题解 P1903 【【模板】分块/带修改莫队（数颜色）】

· · 题解

看了楼下的题解，表示什么都看不懂（我没学过普通莫队。。）

于是决定写份题解。。

原版莫队：

时间复杂度O(n*√n)，不支持修改，就拿本题为例：

如果我们知道(L,R)区间有多少个不同颜色，我们就可以在O(1)的时间求出(L,R+1)或(L+1,R)或(L-1,R)或(L,R-1)的值

举个例子，

5个数，颜色分别为2 3 1 4 5

我们知道(2,3)的答案为2，要知道(2,4)的答案，我们只需要判断color[4]是否出现过，如果否，那么ans++。无论如何，标记color[4]出现的次数+1。

莫队是一个离线算法，被称为优雅的暴力。

这个算法只是把所有询问记录下来，然后交换回答的顺序，按上面的算法去做。

从(L,R)转移到(L1,R1)的时间复杂度是|L1-L|+|R1-R|，可以证明，整个程序时间复杂度O(n*√n)。 那么怎么交换顺序呢？

只需要先将每个询问的左端点分块，分成√n块，每块√n，最后多出的新开一块，

然后按左端点所在块的序号（L/sqrt(n)）为第一关键词，右端点为第二关键词排序就行了。

排序完直接按之前说的转移状态就行了。

至于带修改莫队，我们需要加一个记录询问的变量X，表示在这个询问之前进行了多少次修改。

并且要记录每次修改，修改的位置，修改前的颜色，修改后的颜色。

和普通莫队一样处理，

当碰到一个询问需要X次修改，而当前只执行了X-3次修改，我们就要执行那3次修改。

同样地，如果当前已经执行了X+3次修改，我们就要倒退3次修改。

大概就是这样。。

可以证明时间复杂度O(n^3/5)

代码丑，，因为我改了太久，，很烦。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <list>
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define dop(i,m,n) for(int i=m;i>=n;i--)
#define lowbit(x) (x&(-x))
#define ll long long
#define INF 2147483647
using namespace std;
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int maxn=10010;
const int maxm=10010;
struct Ask{      //记录询问
    int L,R,X,id,lk;        //L,R询问区域，lk左端点所在块
}A[maxm];
struct Do{        //记录修改
    int x,f,t;      //x位置，f原来的颜色，t修改后的颜色
}D[maxm];
int l,r,a[maxn],n,m,color[maxn],ans,len,m1,m2,x,Ans[maxm],c[maxn];
char ch;
void move(int now,int mode){               
    color[a[now]]+=mode;
    if(!color[a[now]]&&mode==-1) ans--;
    if(color[a[now]]==1&&mode==1) ans++;
}
int cmp(const Ask &A,const Ask &B){
    if(A.lk==B.lk) return A.R<B.R;
    return A.lk<B.lk;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    len=(int)sqrt(n);   //块的大小
    rep(i,1,n)
       cin>>a[i],c[i]=a[i];      //把a数组备份
    rep(i,1,m){
       cin>>ch;
       if(ch=='Q'){
         cin>>A[++m1].L;             //m1询问次数
         cin>>A[m1].R;
         A[m1].X=m2;
         A[m1].id=m1;
         A[m1].lk=(A[m1].L-1)/len+1;  
       }
       else{       //m2修改次数
         cin>>D[++m2].x;     //修改的位置
         D[m2].f=a[D[m2].x];  //保存原来的颜色
         cin>>D[m2].t;       //读入修改后的颜色
         a[D[m2].x]=D[m2].t;  //修改颜色
       }
    }
    rep(i,1,n) a[i]=c[i];   //把a数组还原
    color[a[1]]=1;
    ans=1;
    l=r=1;
    sort(A+1,A+m1+1,cmp);    //把询问排序
    rep(i,1,m1){   //一个一个处理
                         //莫队
       while(x<A[i].X){                //x是已执行的修改
         Do tmp=D[++x];
         if(l<=tmp.x&&r>=tmp.x){
           color[a[tmp.x]]--;
           ans-=!color[a[tmp.x]];
           a[tmp.x]=tmp.t;
           color[a[tmp.x]]++;
           ans+=color[a[tmp.x]]==1;
         }
         a[tmp.x]=tmp.t;
       }
       while(x>A[i].X){
         Do tmp=D[x--];
         if(l<=tmp.x&&r>=tmp.x){
           color[a[tmp.x]]--;
           ans-=!color[a[tmp.x]];
           a[tmp.x]=tmp.f;
           color[a[tmp.x]]++;
           ans+=color[a[tmp.x]]==1;
         }
         a[tmp.x]=tmp.f;
       }
       Ask tmp=A[i];
       while(l<tmp.L) move(l-0,-1),l++;       //普通莫队
       while(l>tmp.L) move(l-1,+1),l--;
       while(r<tmp.R) move(r+1,+1),r++;
       while(r>tmp.R) move(r+0,-1),r--;
       Ans[tmp.id]=ans;
    }
    rep(i,1,m1) printf("%d\n",Ans[i]);
    return 0;
}