BZOJ2120
思路：
同时支持修改，查询两种操作的莫队算法，就是带修莫队。
用两个结构体分别记录查询，修改操作；
对查询操作分区：
先将所有的查询操作分为n/unit个区块，
除了考虑l，r所在的区块，还要考虑查询的时间，均为递增排序，对所有的查询排序。
（复杂度（复杂度分析，除了要分析的那个变量是不确定的外，其他的变量全部固定不变，然后分析变量是如何变化的）：
l的复杂度O(unti*m)
{只考虑l的情况，它们的l都是不同的，l至多有m种情况，每次至多变化unit*2次，所以最坏的复杂度是O(unit*m)}
r的复杂度O(n*n/unit)
{只考虑r的情况，此时l已经在同一个区间内了，r有m种情况，每次至多变化n/unit次，所以最坏的情况就是O(n*n/unit)，}
tim的复杂度O((n/unit)*(n/unit))
{只考虑tim的情况，此时n与m在同一个数量级上，可以相互替换l至多前进或者后退n/unit次，r同理，
所以复杂度为O((n/unit)*(n/unit))。}
总复杂度为O(unit*n+n*n/unit+(n/unit)*(n/unit)),当unit = pow(n,2/3)时，复杂度为O(pow(n,5/3),此时的复杂度最小)
）
从区间[1,0]，T = 0开始，此时ans = 0，先更新时间，然后更新左右区间的值，
然后得到这个区间内的不同颜色的笔画的数量，记录答案。
参考文章
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int maxn = 1e6+10; const double IO = 2.0/3.0; //a数组记录每个位置糖果的不同颜色，col记录每个位置的不同颜色的数量； //Ki数组记录每个颜色所在的区间，res数组记录最终的结果 //now数组记录每次修改后的每个位置的颜色 //ans记录某一次的区间[l,r]内的不同颜色的数量，l，r分别表示区间的两个边界，因为修改颜色时要用到，所以设置为全局变量。 int a[maxn],col[maxn]={0},Ki[maxn]={0},res[maxn] = {0},now[maxn] = {0},ans = 0,l = 1,r = 0; struct Node{ //记录查询操作 int id,l,r,tim; //id表示第几个查询操作，l，r分别表示查询区间的左右边界，tim表示这次查询之前最近的一次修改的时间。 Node(){} Node(int x,int y,int z,int w):id(x),l(y),r(z),tim(w){} }qu[maxn]; struct node{ int pos,nxt,pre; //pos表示修改的颜色的位置，nxt表示改变后的颜色，pre表示改变前的颜色 node(){} node(int x,int y,int z):pos(x),nxt(y),pre(z){} }ca[maxn]; bool cmp(Node a,Node b){ //对查询数据进行分块排序，如果左右边界所在的区块相同，按照时间的先后顺序排列。 if(Ki[a.l]==Ki[b.l]){ if(Ki[a.r]==Ki[b.r]) return a.tim<b.tim; return a.r<b.r; } return a.l<b.l; } void Add(int x,int d){ //修改区间[l，r]内的颜色x的数量 col[x]+=d; //颜色x的数量的该变量为d if(d>0){ //颜色的数量增加，如果这个颜色从无到有，说明区间内的颜色种类数+1，ans+1 ans += (col[x]==1); } if(d<0){//颜色的数量减少，如果这个颜色的数量变为0，说明这个区间的颜色种类数-1，ans-1 ans -= (col[x]==0); } } void Go(int x,int y){ //将x位置的颜色修改为颜色y if(l<=x&&x<=r){ Add(y,1); //颜色y的数量+1 Add(a[x],-1);//颜色a[x]的数量-1 } a[x] = y;//修改a位置的颜色 } int main(void) { int n,m; scanf("%d%d",&n,&m); int unit = (int)pow(n,IO); //对n分区 for(int i=1;i<=n;i++) scanf("%d",&a[i]),now[i] = a[i],Ki[i] = i/unit+1; int t1 = 0,t2 = 0; for(int i=1;i<=m;i++){ char ss[5];int x,y; scanf("%s%d%d",ss,&x,&y); if(ss[0]=='Q'){//查询 qu[++t1] = Node(t1,x,y,t2); }else{//修改 ca[++t2] = node(x,y,now[x]);now[x] = y; } } sort(qu+1,qu+1+t1,cmp); int T = 0; for(int i=1;i<=t1;i++){ while(T<qu[i].tim){ //提前到tim时间 Go(ca[T+1].pos,ca[T+1].nxt);T++; } while(T>qu[i].tim){ //退后到tim时间 Go(ca[T].pos,ca[T].pre);T--; } while(l<qu[i].l){ Add(a[l],-1);l++;//l右移，颜色a[l]的数量-1 } while(l>qu[i].l){ Add(a[l-1],1);l--; //l左移，颜色a[l-1]的数量+1 } while(r<qu[i].r){ Add(a[r+1],1);r++;//r右移，颜色a[r+1]的数量+1 } while(r>qu[i].r){ Add(a[r],-1);r--;//r左移，颜色a[r]的数量-1 } res[qu[i].id] = ans;//记录结果。 } for(int i=1;i<=t1;i++) printf("%d\n",res[i]); return 0; }
