1 条题解
-
1
显然，最难操作的其实是 操作。
既然颜色为 的都加上一个数，那么考虑设 表示颜色 一共加了多少。
考虑怎么变颜色呢，很容易发现如果颜色由 变成 ，那么线段树对应节点 。
最后询问的时候把 加上就好了。
代码
#include<bits/stdc++.h> #define mid (l+r>>1) #define seg int p,int l,int r #define lid p<<1,l,mid #define rid p<<1|1,mid+1,r #define int long long using namespace std; const int N=1e6+5; int sum[N],n,m; struct segtree{int s,c,laS,laC;}tr[N<<2]; void pd(seg){ int s=tr[p].laS,c=tr[p].laC; if(s)tr[p<<1].s+=s,tr[p<<1|1].s+=s,tr[p<<1|1].laS+=s,tr[p<<1].laS+=s; if(c)tr[p<<1].c=tr[p<<1|1].c=tr[p<<1].laC=tr[p<<1|1].laC=c; tr[p].laS=tr[p].laC=0; } void work(seg,int L,int R){ if(l>=L&&r<=R&&tr[p].c){ tr[p].s+=sum[tr[p].c]; tr[p].laS+=sum[tr[p].c]; return; } if(tr[p].laS||tr[p].laC)pd(p,l,r); if(L<=mid)work(lid,L,R); if(R>mid)work(rid,L,R); tr[p].s=tr[p<<1].s+tr[p<<1|1].s; } void add(seg,int L,int R,int z){ if(l>=L&&r<=R){ tr[p].s-=sum[z]; tr[p].laS-=sum[z]; tr[p].c=z; tr[p].laC=z; return; } if(tr[p].laS||tr[p].laC)pd(p,l,r); if(L<=mid)add(lid,L,R,z); if(R>mid)add(rid,L,R,z); tr[p].s=tr[p<<1].s+tr[p<<1|1].s; tr[p].c=(tr[p<<1].c==tr[p<<1|1].c?tr[p<<1].c:0); } int ask(seg,int x){ if(l==r)return tr[p].s+sum[tr[p].c]; if(tr[p].laS||tr[p].laC)pd(p,l,r); if(x<=mid)return ask(lid,x); else return ask(rid,x); } void build(seg){ tr[p].c=1; if(l==r)return; build(lid),build(rid); } signed main(){ scanf("%lld%lld",&n,&m); build(1,1,n); for(int i=1;i<=m;i++){ char st[10]; int l,r,z; scanf("%s",st); if(st[0]=='C'){ scanf("%lld%lld%lld",&l,&r,&z); work(1,1,n,l,r); add(1,1,n,l,r,z); } if(st[0]=='A')scanf("%lld%lld",&l,&z),sum[l]+=z; if(st[0]=='Q')scanf("%lld",&l),printf("%lld\n",ask(1,1,n,l)); } }
- 1
