SP30906 ADAUNIQ - Ada and Unique Vegetable
带修莫队。
首先观察题面，然后数据范围一看带修莫队过不了，但这并不妨碍我们玄学起来。
于是这道题特征是“某一个值的出现次数”，再加上单点修改，显然可以使用带修莫队维护。
然后就没有了。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000005,M=2000005;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-'){f=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int a[N],pos[N],n,m,ANS[N],ans,cnt[N],cnt1,cnt2,l=1,r;
struct node{int ql,qr,t,id;}q[N];
struct node1{int p,x;}c[N];
inline bool cmp(node x,node y){
if(pos[x.ql]!=pos[y.ql])return x.ql<y.ql;
if(pos[x.qr]!=pos[y.qr])return x.qr<y.qr;
return x.t<y.t;
}
inline void update(int id,int f){
int x=a[id];
cnt[x]+=f;
if(f==1&&cnt[x]==1) ans++;
if(f==-1&&cnt[x]==0) ans--;
if(f==1&&cnt[x]==2) ans--;
if(f==-1&&cnt[x]==1) ans++;
return ;
}
inline void change(int id){
if(c[id].p>=l&&c[id].p<=r){
cnt[a[c[id].p]]--;
if(cnt[a[c[id].p]]==0) ans--;
if(cnt[a[c[id].p]]==1) ans++;
if(cnt[c[id].x]==0) ans++;
if(cnt[c[id].x]==1) ans--;
cnt[c[id].x]++;
}
swap(c[id].x,a[c[id].p]);
return ;
}
signed main(){
n=read(),m=read();
int op=pow(n,2.0/3.0);
for(int i=1;i<=n;i++){
a[i]=read();
pos[i]=i/op;
}
for(int i=1;i<=m;i++){
int oop=read();
if(oop==2) q[++cnt1].ql=read()+1,q[cnt1].qr=read()+1,q[cnt1].id=cnt1,q[cnt1].t=cnt2;
else c[++cnt2].p=read()+1,c[cnt2].x=read();
}
sort(q+1,q+cnt1+1,cmp);
for(int i=1,t=0;i<=m;i++){
while(l<q[i].ql) update(l++,-1);
while(l>q[i].ql) update(--l,1);
while(r<q[i].qr) update(++r,1);
while(r>q[i].qr) update(r--,-1);
while(t<q[i].t) change(++t);
while(t>q[i].t) change(t--);
ANS[q[i].id]=ans;
}
for(int i=1;i<=cnt1;i++) printf("%d
",ANS[i]);
return 0;
}