首页 > 代码库 > cogs 1901. [国家集训队2011]数颜色
cogs 1901. [国家集训队2011]数颜色
Cogs 1901. [国家集训队2011]数颜色
★★★ 输入文件：nt2011_color.in 输出文件：nt2011_color.out 简单对比
时间限制：0.6 s 内存限制：512 MB
【试题来源】
2011中国国家集训队命题答辩
【问题描述】
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
【输入格式】
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
【输出格式】
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
【样例输入】
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
【样例输出】
4
4
3
4
4
3
4
【数据规模和约定】
对于40%数据，只包含第一类操作（无修改操作），且。 除此之外的20%的数据，N，M≤1000 对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。 时间限制：0.6s
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;#define maxn 100050struct nodeQ{ int l,r,t,id;}a[maxn];struct nodeR{ int pos,x,h;}b[maxn];bool if_[maxn];int bel[maxn],ai[maxn],tot,num,ans[maxn],ti[maxn*10];int n,m,size=440,now;int cmp(nodeQ x,nodeQ y){ if(bel[x.l]==bel[y.l]){ if(bel[x.r]==bel[y.r])return x.t<y.t; return x.r<y.r; } return x.l<y.l;}inline void change(int x){ int pos=b[x].pos; if(if_[pos]){ ti[ai[pos]]--; if(!ti[ai[pos]])now--; } b[x].h=ai[pos]; ai[pos]=b[x].x; if(if_[pos]){ if(!ti[ai[pos]])now++; ti[ai[pos]]++; }}inline void unchange(int x){ int pos=b[x].pos; if(if_[pos]){ ti[ai[pos]]--; if(!ti[ai[pos]])now--; } ai[pos]=b[x].h; if(if_[pos]){ if(!ti[ai[pos]])now++; ti[ai[pos]]++; }}inline void update(int to,int x){ int pre=ti[ai[to]]; ti[ai[to]]+=x; if(ti[ai[to]]==0&&pre==1)now--; if(ti[ai[to]]==1&&pre==0)now++; if(x==1)if_[to]=true; else if_[to]=false;}int main(){ //freopen("cola.txt","r",stdin); freopen("nt2011_color.in","r",stdin); freopen("nt2011_color.out","w",stdout); scanf("%d%d",&n,&m);char ch[4];int l,r,t; for(int i=1;i<=n;i++)scanf("%d",&ai[i]),bel[i]=(i-1)/size+1; for(int i=1;i<=m;i++){ scanf("%s%d%d",ch,&l,&r); if(ch[0]==‘Q‘)a[++tot].l=l,a[tot].r=r,a[tot].t=num,a[tot].id=tot; else b[++num].pos=l,b[num].x=r; } sort(a+1,a+tot+1,cmp);l=1,r=0,t=0,now=0; for(int i=1;i<=tot;i++){ while(t<a[i].t)t++,change(t); while(t>a[i].t)unchange(t),t--; while(r<a[i].r)r++,update(r,1); while(r>a[i].r)update(r,-1),r--; while(l<a[i].l)update(l,-1),l++; while(l>a[i].l)l--,update(l,1); ans[a[i].id]=now; } for(int i=1;i<=tot;i++)printf("%d\n",ans[i]); return 0;}
cogs 1901. [国家集训队2011]数颜色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。