欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

题解 【国家集训队2011】数颜色

发布时间:2024/7/5 编程问答 0 豆豆
如意编程网 收集整理的这篇文章主要介绍了 题解 【国家集训队2011】数颜色 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题面

 

解析

这题也就是一个带修改的莫队啊啊!!

所以,我们只需要在普通莫队上加上一维时间即可。

怎么加呢?

只需要记录下每次修改和查询的时间,

在左右端点跳跃的同时,也将时间跳到询问的时间就行了。

 

具体看代码吧:

// luogu-judger-enable-o2 #include<bits/stdc++.h> using namespace std;inline int read(){int sum=0,f=1;char ch=getchar();while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}return f*sum; }struct node{int l,r,id,ti; }q[100001]; struct chang{int pla/*第几支笔*/,to/*颜色*/; }c[100001]; int n,m,qsum,csum; int l,r,timn,gap; int a[100001],ans=0,bl[100001]; int sum[1000001]; int ansn[100001]; char opt[5];bool cmp(node a,node b) {if(bl[a.l] == bl[b.l]){if(bl[a.r] == bl[b.r]) return a.ti < b.ti;return a.r < b.r; }return a.l < b.l; }inline void add(int x){if(!(sum[a[x]]++)) ans++; }inline void del(int x){if(!(--sum[a[x]])) ans--; }inline void change(int ti,int i){if(c[ti].pla>=q[i].l&&c[ti].pla<=q[i].r) {if(!(--sum[a[c[ti].pla]])) ans--;if(!(sum[c[ti].to]++)) ans++;}swap(a[c[ti].pla],c[ti].to); }int main(){//freopen("data12.in","r",stdin);n=read();m=read();gap=n/sqrt(m*2.0/3.0);//gap=sqrt(n);for(int i=1;i<=n;i++) bl[i]=(i-1)/gap+1; for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=m;i++){cin>>opt;if(opt[0]=='Q'){q[++qsum].id=qsum;q[qsum].l=read();q[qsum].r=read();q[qsum].ti=csum;}else if(opt[0]=='R'){c[++csum].pla=read();c[csum].to=read();}ansn[q[i].id]=ans;}sort(q+1,q+qsum+1,cmp);l=1;r=0;timn=0;for(int i=1;i<=qsum;i++){int ql=q[i].l,qr=q[i].r;int qtime=q[i].ti;while(l<ql) del(l++);while(l>ql) add(--l); while(r>qr) del(r--); while(r<qr) add(++r);while(timn<qtime) change(++timn,i);while(timn>qtime) change(timn--,i); ansn[q[i].id]=ans;}for(int i=1;i<=qsum;i++){printf("%d\n",ansn[i]);}return 0; }

 

转载于:https://www.cnblogs.com/zsq259/p/10563632.html

总结

以上是如意编程网为你收集整理的题解 【国家集训队2011】数颜色的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。