[oi-wiki](https://oi-wiki.org/misc/modifiable-mo-algo/)上有个~~奇怪的~~证明证了后者的复杂度
by Aranea晨曦 @ 2022-07-16 19:30:12
@[Aranea晨曦](/user/176849) 但前者的复杂度也有比较严谨的证明啊，还是说我代码有问题
```
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5e4,S=1e6+10;
int n,m,T,len,res,w[N],ans[N],cnt[S];
struct Quary
{
int id,l,r,t;
}Q[N];
struct Change
{
int v,x;
}C[N];
inline int get(int x)
{
return x/len;
}
bool cmp(Quary X,Quary Y)
{
int a,b;
a=get(X.l),b=get(Y.l);
if(a!=b) return a<b;
a=get(X.r),b=get(Y.r);
if(a!=b) return a<b;
return X.t<Y.t;
}
inline void add(int x)
{
if(!cnt[x]) res++;
cnt[x]++;
}
inline void del(int x)
{
cnt[x]--;
if(!cnt[x]) res--;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++)
{
char ch[2];
int a,b;
scanf("%s%d%d",ch,&a,&b);
if(ch[0]=='Q') Q[i-T]={i-T,a,b,T};
else C[++T]={a,b};
}
//len=pow((double)n*T,1.0/3)+1;
//这是我TLE的写法
len=pow(n,2.0/3)+1;
sort(Q+1,Q+m-T+1,cmp);
for(int i=1,j=0,t=0,k=1;k<=m-T;k++)
{
int L=Q[k].l,R=Q[k].r,time=Q[k].t;
while(i<L) del(w[i++]);
while(i>L) add(w[--i]);
while(j<R) add(w[++j]);
while(j>R) del(w[j--]);
while(t<time)
{
t++;
if(C[t].v>=L&&C[t].v<=R)
{
del(w[C[t].v]);
add(C[t].x);
}
swap(w[C[t].v],C[t].x);
}
while(t>time)
{
if(C[t].v>=L&&C[t].v<=R)
{
del(w[C[t].v]);
add(C[t].x);
}
swap(w[C[t].v],C[t].x);
t--;
}
ans[Q[k].id]=res;
}
for(int i=1;i<=m-T;i++) printf("%d\n",ans[i]);
return 0;
}
```
by Demeanor_Roy @ 2022-07-16 19:37:47
草，我找了一圈没找到前面那个的说法（
[只看到了用式子算的n^2/3的](https://www.cnblogs.com/zaza-zt/p/14990713.html)
我太蒻了，我也不知道
by Aranea晨曦 @ 2022-07-16 19:48:43