闵行区天气_gg模板网_山西网络营销seo_seo优化工作内容

原题链接

给你一个序列，多次询问 $[l,r]$ 中出现的不同数的个数。这个我会！询问离线，然后树状数组——怎么还带修改？这个时候就要请出带修莫队了。

莫队算法可以以 $O(m\sqrt{n})$ 的时间复杂度解决一些区间询问，支持离线的问题。带上修改操作也不难维护，只需要增加一个 $t$，表示该次询问前有几次修改，然后加上 $t$ 指针的维护即可。排序时先按 $l,r$ 排序，若 $l,r$ 相等再按 $t$ 从小到大排序。

接下来就是纯板子了，代码很好写的。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,m,a[N],cnt[N],res,ans[N],cnt1,cnt2,pos[N],vis[N];
struct node{int l,r,x,y,t,id;
}q1[N],q2[N];
bool cmp(node a,node b){if(pos[a.l]==pos[b.l]){if(pos[a.r]==pos[b.r]) return a.t<b.t;return pos[a.r]<pos[b.r];}return pos[a.l]<pos[b.l];
}
void del(int x){cnt[x]--;if(!cnt[x]) res--;
}
void add(int x){cnt[x]++;if(cnt[x]==1) res++;
}
void update(int i,int t){if(q1[i].l<=q2[t].x&&q1[i].r>=q2[t].x){//这次修改能够影响这个区间，我们才更改del(a[q2[t].x]),add(q2[t].y);}swap(a[q2[t].x],q2[t].y);
}
int main(){n=read(),m=read();int sz=pow(n,0.666);for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) pos[i]=(i-1)/sz+1;for(int i=1;i<=m;i++){char op;cin>>op;int x=read(),y=read();if(op=='Q') q1[++cnt1]={x,y,0,0,cnt2,i},vis[i]=1;else q2[++cnt2]={0,0,x,y,0,i};}sort(q1+1,q1+1+cnt1,cmp);for(int i=1,l=0,r=0,tt=0;i<=cnt1;i++){while(l<q1[i].l) del(a[l++]);while(r>q1[i].r) del(a[r--]);while(l>q1[i].l) add(a[--l]);while(r<q1[i].r) add(a[++r]);while(tt<q1[i].t) update(i,++tt);while(tt>q1[i].t) update(i,tt--);ans[q1[i].id]=res;}for(int i=1;i<=m;i++) if(vis[i]) cout<<ans[i]<<endl;return 0;
}