大概是一道带修莫队的裸题，然而还是WA了无数次，真是太弱了......
千万要记得带修的话前驱和后驱都要记录
都要记录！
要记录！
记录！
录！
！
#include<iostream> #include<cstdlib> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int maxn=10005; const int maxm=1000005; struct query { int id,l,r,t,block; }q[maxn]; struct change { int pre,sub,pos;//注意向前扫和向后扫变的值不一样，需要记录pre和sub }c[maxn]; int n,m,cnt,tot; int a[maxn]; int last[maxn]; int num[maxm]; int ans[maxn]; bool cmp(query x,query y) { return x.block<y.block||(x.block==y.block&&x.r<y.r) ||(x.block==y.block&&x.r==y.r&&x.t<y.t); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",a+i),last[i]=a[i]; int bl=(int)pow(n,2.0/3.0); char in[5]; for(int i=1;i<=m;i++) { scanf("%s",in); if(in[0]=='Q') { ++cnt; scanf("%d%d",&q[cnt].l,&q[cnt].r); q[cnt].block=(q[cnt].l-1)/bl+1; q[cnt].id=cnt; q[cnt].t=tot; } else { ++tot; scanf("%d%d",&c[tot].pos,&c[tot].sub); c[tot].pre=last[c[tot].pos]; last[c[tot].pos]=c[tot].sub; } } sort(q+1,q+cnt+1,cmp); int l=1,r=0,t=0,res=0; for(int i=1;i<=cnt;i++) { while(q[i].t>t) { t++; if(l<=c[t].pos&&c[t].pos<=r) { num[a[c[t].pos]]--; if(!num[a[c[t].pos]])res--; a[c[t].pos]=c[t].sub; if(!num[a[c[t].pos]])res++; num[a[c[t].pos]]++; } else a[c[t].pos]=c[t].sub; } while(q[i].t<t) { if(l<=c[t].pos&&c[t].pos<=r) { num[a[c[t].pos]]--; if(!num[a[c[t].pos]])res--; a[c[t].pos]=c[t].pre; if(!num[a[c[t].pos]])res++; num[a[c[t].pos]]++; } else a[c[t].pos]=c[t].pre; t--; } while(l>q[i].l) { l--; if(!num[a[l]])res++; num[a[l]]++; } while(r<q[i].r) { r++; if(!num[a[r]])res++; num[a[r]]++; } while(l<q[i].l) { num[a[l]]--; if(!num[a[l]])res--; l++; } while(r>q[i].r) { num[a[r]]--; if(!num[a[r]])res--; r--; } ans[q[i].id]=res; } for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]); return 0; }
然后还有一个搜到的做法，学习了一个奇怪的树套树。
主席树中一个节点的修改会牵扯很多棵树，暴力修改的复杂度是O(nlogn)，太过于庞大，于是采用一种机智的做法，利用lowbit的特性记录修改轨迹。
树状数组可以记录一个数向上更新的轨迹，本来数更新一个数组c[i]，现在将这个更新改为更新一个主席树，值设为需要更新的数（注意修改节点的值）。查询时向下累加，计算牵扯的节点总共的修改总值，然后和原静态主席树的ans叠加即可得到修改后的正确值。
然后对于这道题，先搞个离散是毋庸置疑的。而查询[l,r]中的第一次出现的数的总个数，那么可以改为查询它的前驱在l之前的节点数有多少。在一棵以pos为下标的线段树上查询值小于l的个数有多少？很明显需要n查询。而思考一下对于一棵计数线段树，其下标为数值，查询[1,l]范围的数的个数只需要查询[1,l]范围内的sum，而对于一列数来说则需要一列线段树，用树状数组联系这一列线段树，支持其修改和查询操作。而这一列线段树的根是彩笔的位置，其上的叶节点表示当前彩笔颜色的前驱（即前一个颜色相同的彩笔的位置，建立的也是一个位置图），然后查询[1,r]范围内值小于l的，即每棵线段树求一下[1,l]的sum。要转化为题目要求的[l,r]区间，只需查分一下即可。
由于每个颜色会出现多次，每个颜色插入和查询都需要一棵平衡树，于是每个颜色建立set（STL真好233），注意当it为终结点的情况的判断。
N.B.注释内容为易错的小细节。
注意数据范围为10000+1000。。。
#include<iostream> #include<cstdlib> #include<cstring> #include<set> #include<cstdio> #include<algorithm> using namespace std; const int maxn=11005; struct tree { int lson,rson,val; }t[maxn*120]; int n,m,num,cnt; int disc[maxn]; int a[maxn],last[maxn]; int root[maxn],c[maxn]; bool q[maxn]; pair<int,int>node[maxn]; set<int>col[maxn]; set<int>::iterator it,pre,sub; void build_init(int &ro,int l,int r)//静态主席树 { ro=++cnt; if(l==r)return; int mid=l+r>>1; build_init(t[ro].lson,l,mid); build_init(t[ro].rson,mid+1,r); } void build_seg(int pre,int &ro,int pos,int val,int l,int r)//静态主席树 { ro=++cnt; t[ro]=t[pre];// t[ro].val+=val; if(l==r)return; int mid=l+r>>1; if(pos<=mid)build_seg(t[pre].lson,t[ro].lson,pos,val,l,mid); else build_seg(t[pre].rson,t[ro].rson,pos,val,mid+1,r); } void update_seg(int &ro,int pos,int val,int l,int r)//动态修改主席树 { if(!ro)ro=++cnt; t[ro].val+=val; if(l==r)return; int mid=l+r>>1; if(pos<=mid)update_seg(t[ro].lson,pos,val,l,mid); else update_seg(t[ro].rson,pos,val,mid+1,r); } int query_seg(int ro,int maxi,int l,int r) { if(r==maxi)return t[ro].val; int mid=l+r>>1; if(maxi<=mid)return query_seg(t[ro].lson,maxi,l,mid); else return t[t[ro].lson].val+query_seg(t[ro].rson,maxi,mid+1,r); } void update_tree(int x,int pos,int val) { int tmp; for(int i=x;i<=n;i+=i&-i) update_seg(c[i],pos,val,0,n); } int query(int x,int maxi) { int res=query_seg(root[x],maxi,0,n); for(int i=x;i;i-=i&-i) res+=query_seg(c[i],maxi,0,n); return res; } int main() { scanf("%d%d",&n,&m); num=n; for(int i=1;i<=n;i++) scanf("%d",a+i),disc[i]=a[i]; char judge[2]; int x,y; for(int i=1;i<=m;i++) { scanf("%s%d%d",judge,&node[i].first,&node[i].second); if(judge[0]=='Q') q[i]=true; else disc[++num]=node[i].second; } sort(disc+1,disc+num+1); num=unique(disc+1,disc+num+1)-(disc+1); for(int i=1;i<=n;i++) a[i]=lower_bound(disc+1,disc+num+1,a[i])-disc; build_init(root[0],0,n); for(int i=1;i<=num;i++)col[i].insert(0);// for(int i=1;i<=n;i++) { build_seg(root[i-1],root[i],last[a[i]],1,0,n); last[a[i]]=i; col[a[i]].insert(i); } for(int i=1;i<=m;i++) { if(q[i]) printf("%d\n",query(node[i].second,node[i].first-1)-query(node[i].first-1,node[i].first-1)); else { int pos=node[i].first; int newcol=node[i].second; newcol=lower_bound(disc+1,disc+num+1,newcol)-disc; it=pre=sub=col[a[pos]].lower_bound(pos); pre--;sub++; update_tree(*it,*pre,-1); if(sub!=col[a[pos]].end()) update_tree(*sub,*it,-1), update_tree(*sub,*pre,1); col[a[pos]].erase(it); a[pos]=newcol; col[a[pos]].insert(pos); it=pre=sub=col[a[pos]].lower_bound(pos); pre--;sub++; update_tree(*it,*pre,1); if(sub!=col[a[pos]].end()) update_tree(*sub,*it,1), update_tree(*sub,*pre,-1); } } return 0; }