口胡cmp的锅
r排反了？
by UnyieldingTrilobite @ 2020-03-05 07:41:14
确实这题卡常。。。
by Fatalis_Lights @ 2020-03-05 07:50:35
@[帅气伙小](/user/155626) 本题的块大小不是$O(n^\frac{2}{3})$，而是$O((n+Q)^\frac{2}{3})$
by Smile_Cindy @ 2020-03-05 08:25:25
@[帅气伙小](/user/155626) 好吧块开4000还是救不了你，
给你看下我的代码吧
```cpp
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAX_N=150000,MAX_M=1000005,B=4000;
int res[MAX_N],n,m;
int A[MAX_N],last[MAX_N];
int cnt[MAX_M];
struct node
{
int bl,l,br,r,t,id;
}q[MAX_N];
int cnt_q;
bool operator < (node p1,node p2)
{
return p1.bl<p2.bl || p1.bl==p2.bl && p1.br<p2.br || p1.bl==p2.bl && p1.br==p2.br && p1.t<p2.t;
}
int from[MAX_N],to[MAX_N],pos[MAX_N],cnt_c;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>A[i];
for(int i=1;i<=n;i++)last[i]=A[i];
for(int i=1;i<=m;i++)
{
string opt;
cin>>opt;
if(opt=="Q")
{
int l,r;
cin>>l>>r;
cnt_q++;
q[cnt_q].id=cnt_q;
q[cnt_q].l=l;
q[cnt_q].r=r;
q[cnt_q].bl=l/B;
q[cnt_q].br=r/B;
q[cnt_q].t=cnt_c;
}
else
{
int x,y;
cin>>x>>y;
cnt_c++;
pos[cnt_c]=x;
from[cnt_c]=last[x];
to[cnt_c]=y;
last[x]=y;
}
}
sort(q+1,q+cnt_q+1);
int ans=0;
int l=q[1].l,r=q[1].r,t=q[1].t;
for(int i=1;i<=t;i++)A[pos[i]]=to[i];
for(int i=l;i<=r;i++)
{
cnt[A[i]]++;
ans+=(cnt[A[i]]==1);
}
for(int i=1;i<=cnt_q;i++)
{
int ql=q[i].l,qr=q[i].r,qt=q[i].t;
while(t<qt)
{
t++;
A[pos[t]]=to[t];
if(pos[t]>=l && pos[t]<=r)
{
ans-=(cnt[from[t]]--==1);
ans+=(cnt[to[t]]++==0);
}
}
while(t>qt)
{
A[pos[t]]=from[t];
if(pos[t]>=l && pos[t]<=r)
{
ans-=(cnt[to[t]]--==1);
ans+=(cnt[from[t]]++==0);
}
t--;
}
while(l>ql)ans+=(++cnt[A[--l]]==1);
while(r<qr)ans+=(++cnt[A[++r]]==1);
while(l<ql)ans-=(cnt[A[l++]]--==1);
while(r>qr)ans-=(cnt[A[r--]]--==1);
res[q[i].id]=ans;
}
for(int i=1;i<=cnt_q;i++)cout<<res[i]<<endl;
return 0;
}
```
by Smile_Cindy @ 2020-03-05 08:27:36
@[Alpha](/user/87058) 排序的问题，真的玄学问题
by 老咸鱼了 @ 2020-03-05 14:50:51