P1903 [国家集训队] 数颜色 / 维护队列

原题链接
给你一个序列，多次扣问                                    [                         l                         ,                         r                         ]                              [l,r]                  [l,r] 中出现的差别数的个数。这个我会！扣问离线，然后树状数组——怎么还带修改？这个时间就要请出带修莫队了。
莫队算法可以以                                    O                         (                         m                                   n                                  )                              O(m\sqrt n)                  O(mn            ​) 的时间复杂度办理一些区间扣问，支持离线的问题。带上修改操纵也不难维护，只必要增长一个                                    t                              t                  t，表现该次扣问前有几次修改，然后加上                                    t                              t                  t 指针的维护即可。排序时先按                                    l                         ,                         r                              l,r                  l,r 排序，若                                    l                         ,                         r                              l,r                  l,r 相称再按                                    t                              t                  t 从小到大排序。
接下来就是纯板子了，代码很好写的。

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=1e6+10;
4. int read(){
5.         int x=0,f=1;char ch=getchar();
6.         while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
7.         while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
8.         return x*f;
9. }
10. int n,m,a[N],cnt[N],res,ans[N],cnt1,cnt2,pos[N],vis[N];
11. struct node{
12.         int l,r,x,y,t,id;
13. }q1[N],q2[N];
14. bool cmp(node a,node b){
15.         if(pos[a.l]==pos[b.l]){
16.                 if(pos[a.r]==pos[b.r]) return a.t<b.t;
17.                 return pos[a.r]<pos[b.r];
18.         }
19.         return pos[a.l]<pos[b.l];
20. }
21. void del(int x){
22.         cnt[x]--;if(!cnt[x]) res--;
23. }
24. void add(int x){
25.         cnt[x]++;if(cnt[x]==1) res++;
26. }
27. void update(int i,int t){
28.         if(q1[i].l<=q2[t].x&&q1[i].r>=q2[t].x){//这次修改能够影响这个区间，我们才更改
29.                 del(a[q2[t].x]),add(q2[t].y);
30.         }
31.         swap(a[q2[t].x],q2[t].y);
32. }
33. int main(){
34.         n=read(),m=read();int sz=pow(n,0.666);
35.         for(int i=1;i<=n;i++) a[i]=read();
36.         for(int i=1;i<=n;i++) pos[i]=(i-1)/sz+1;
37.         for(int i=1;i<=m;i++){
38.                 char op;cin>>op;int x=read(),y=read();
39.                 if(op=='Q') q1[++cnt1]={x,y,0,0,cnt2,i},vis[i]=1;
40.                 else q2[++cnt2]={0,0,x,y,0,i};
41.         }
42.         sort(q1+1,q1+1+cnt1,cmp);
43.         for(int i=1,l=0,r=0,tt=0;i<=cnt1;i++){
44.                 while(l<q1[i].l) del(a[l++]);
45.                 while(r>q1[i].r) del(a[r--]);
46.                 while(l>q1[i].l) add(a[--l]);
47.                 while(r<q1[i].r) add(a[++r]);
48.                 while(tt<q1[i].t) update(i,++tt);
49.                 while(tt>q1[i].t) update(i,tt--);
50.                 ans[q1[i].id]=res;
51.         }
52.         for(int i=1;i<=m;i++) if(vis[i]) cout<<ans[i]<<endl;
53.         return 0;
54. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。