[C++知识库]CF1638E colorful operations

考虑用线段树维护。
如果某一段颜色相同，均为$x$，那么把这一段颜色改为$y$相当于先加上目前颜色$laz[x]$的贡献然后减去之后颜色$laz[y]$的贡献。$query$的时候输出$query(x)+laz[color[x]]$即可，因为每次修改颜色的时候对区间赋值，所以复杂度被均摊。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define ms l+r>>1
#define ls p<<1
#define rs p<<1|1
ll lazC[4000005],lazV[4000005];
int color[4000005];
ll LAZ[4000005];
bool cover[4000005];
void pushup(int p,int l,int r)
{
	if(cover[ls]&&cover[rs]&&(color[ls]==color[rs]))
   	{
   		cover[p]=1;
   		color[p]=color[ls];
   	}
   	else cover[p]=0;
}
void build(int p,int l,int r)
{
    cover[p]=1;
    lazC[p]=1;
    color[p]=1;
    if(l==r)return;
    
    int mid=ms;
    build(ls,l,mid);
    build(rs,mid+1,r);
   	
   	pushup(p,l,r);
}
void update(int p,int l,int r,int x,int y,int w);
void pushdown(int p,int l,int r)
{
	if(lazC[p])
	{
		lazC[ls]=lazC[p];
		cover[ls]=1;
		lazC[rs]=lazC[p];
		cover[rs]=1;

		color[ls]=lazC[p];
		color[rs]=lazC[p];
		
		lazC[p]=0;
	}
	if(lazV[p])
	{
		lazV[ls]+=lazV[p];
		lazV[rs]+=lazV[p];
		lazV[p]=0;
	}
}
void update(int p,int l,int r,int x,int y,int w)
{
    if(l>=x&&r<=y&&cover[p])
    {
    	lazV[p]+=LAZ[color[p]]-LAZ[w];

    	lazC[p]=w;
    	color[p]=w;
        return ;
    }
    int mid=ms;
    pushdown(p,l,r);
    if(x<=mid)update(ls,l,mid,x,y,w);
    if(y>mid)update(rs,mid+1,r,x,y,w);
    pushup(p,l,r);
}
long long query(int p,int l,int r,int x)
{
    if(l==r)
    {
    	// printf("color=%d val=%lld\n",color[p],lazV[p]);
    	return lazV[p]+LAZ[color[p]];

    }
    
    pushdown(p,l,r);
    int mid=ms;
    if(x<=mid)return query(ls,l,mid,x);
    else return query(rs,mid+1,r,x);
    pushup(p,l,r);
}
int main()
{
	int n,q;
	scanf("%d%d",&n,&q);
	build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		char s[10];
		scanf("%s",s+1);
		if(s[1]=='C')
		{
			int l,r,c;
			scanf("%d%d%d",&l,&r,&c);
			update(1,1,n,l,r,c);
		}
		else if(s[1]=='A')
		{
			int c,x;
			scanf("%d%d",&c,&x);
			LAZ[c]+=x;
		}
		else if(s[1]=='Q')
		{
			int x;
			scanf("%d",&x);
			printf("%lld\n",query(1,1,n,x));
		}

	}
    return  0;
}