首页 > 代码库 > bzoj 2453: 维护队列
bzoj 2453: 维护队列
2453: 维护队列
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 1079 Solved: 503
[Submit][Status][Discuss]
Description
你小时候玩过弹珠吗？
小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。
Input
输入文件第一行包含两个整数N和M。
第二行N个整数，表示初始队列中弹珠的颜色。
接下来M行，每行的形式为“Q L R”或“R x c”，“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中，一共有多少不同颜色的弹珠，“R x c”表示A把x位置上的弹珠换成了c颜色。
Output
对于每个Q操作，输出一行表示询问结果。
Sample Input
2 3
1 2
Q 1 2
R 1 2
Q 1 2
Sample Output
2
1
1
HINT
对于100%的数据，有1 ≤ N ≤ 10000, 1 ≤ M ≤ 10000，小朋友A不会修改超过1000次，所有颜色均用1到10^6的整数表示。
Source
2011福建集训
带修莫队
#include<cmath>#include<cstdio>#include<algorithm>#define N 10001#define M 1000001using namespace std;int n,m,col[M],sum[M],ans[N];int tot,now,siz,tmp;struct Query{ int l,r,bl,id,tim; bool operator < (Query p) const { if(bl!=p.bl) return bl<p.bl; if(r!=p.r) return r<p.r; return tim<p.tim; }}e[N];struct Change{ int be,af,pos;}g[1001];void update(int p,int w){ sum[p]+=w; if(sum[p]==1 && w==1) tmp++; if(!sum[p] && w==-1) tmp--;}int main(){ scanf("%d%d",&n,&m); siz=sqrt(n); for(int i=1;i<=n;i++) scanf("%d",&col[i]); char s[3]; int l,r; while(m--) { scanf("%s%d%d",s,&l,&r); if(s[0]==‘Q‘) { e[++tot].l=l; e[tot].r=r; e[tot].bl=(l-1)/siz; e[tot].tim=now; e[tot].id=tot; } else { g[++now].pos=l; g[now].af=r; } } sort(e+1,e+tot+1); int L=1,R=0; now=0; for(int i=1;i<=tot;i++) { while(now<e[i].tim) { now++; g[now].be=col[g[now].pos]; if(g[now].pos>=L&&g[now].pos<=R) { update(g[now].be,-1); update(g[now].af,1); } col[g[now].pos]=g[now].af; } while(now>e[i].tim) { if(g[now].pos>=L&&g[now].pos<=R) { update(g[now].af,-1); update(g[now].be,1); } col[g[now].pos]=g[now].be; now--; } while(e[i].l<L) update(col[--L],1); while(e[i].l>L) update(col[L++],-1); while(e[i].r>R) update(col[++R],1); while(e[i].r<R) update(col[R--],-1); ans[e[i].id]=tmp; } for(int i=1;i<=tot;i++) printf("%d\n",ans[i]);}
优化后：
读入优化、1，-1改成 true，false
优化一半
#include<cmath>#include<cstdio>#include<algorithm>#define N 10001#define M 1000001using namespace std;int n,m,col[M],sum[M],ans[N];int tot,now,siz,tmp;struct Query{ int l,r,bl,id,tim; bool operator < (Query p) const { if(bl!=p.bl) return bl<p.bl; if(r!=p.r) return r<p.r; return tim<p.tim; }}e[N];struct Change{ int be,af,pos;}g[1001];void update(int p,bool w){ if(w) { sum[p]++; if(sum[p]==1) tmp++; } else { sum[p]--; if(!sum[p]) tmp--; }}void read(int &x){ x=0; char c=getchar(); while(c<‘0‘||c>‘9‘) c=getchar(); while(c>=‘0‘&&c<=‘9‘) { x=x*10+c-‘0‘; c=getchar(); }}int main(){ read(n); read(m); siz=sqrt(n); for(int i=1;i<=n;i++) read(col[i]); char s[3]; int l,r; while(m--) { scanf("%s",s); read(l); read(r); if(s[0]==‘Q‘) { e[++tot].l=l; e[tot].r=r; e[tot].bl=(l-1)/siz; e[tot].tim=now; e[tot].id=tot; } else { g[++now].pos=l; g[now].af=r; } } sort(e+1,e+tot+1); int L=1,R=0; now=0; for(int i=1;i<=tot;i++) { while(now<e[i].tim) { now++; g[now].be=col[g[now].pos]; if(g[now].pos>=L&&g[now].pos<=R) { update(g[now].be,false); update(g[now].af,true); } col[g[now].pos]=g[now].af; } while(now>e[i].tim) { if(g[now].pos>=L&&g[now].pos<=R) { update(g[now].af,false); update(g[now].be,true); } col[g[now].pos]=g[now].be; now--; } while(e[i].l<L) update(col[--L],true); while(e[i].l>L) update(col[L++],false); while(e[i].r>R) update(col[++R],true); while(e[i].r<R) update(col[R--],false); ans[e[i].id]=tmp; } for(int i=1;i<=tot;i++) printf("%d\n",ans[i]);}
bzoj 2453: 维护队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。