首页 > 代码库 > bzoj 2120

bzoj 2120

2024-10-09 09:23:02   211人阅读

2120: 数颜色

Time Limit: 6 Sec  Memory Limit: 259 MB
Submit: 5161  Solved: 2065
[Submit][Status][Discuss]

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

Output

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

Sample Input

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

Sample Output

4
4
3
4

HINT

 

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。


2016.3.2新加数据两组by Nano_Ape

 

待修改的莫队

让查询与修改操作分离

#include<cmath>#include<cstdio>#include<cstring>#include<algorithm>#define K 2000001#define N 10001#define M 1001using namespace std;int n,m,siz,now,tot,tmp;int col[K],sum[K],original[K];struct QUERY{    int l,r,bl,id,ans;    int tim;    }e[N];struct CNANGE{    int before,after,pos;}ch[M];bool cmp1(QUERY q,QUERY p){    if(q.bl!=p.bl) return q.bl<p.bl;    if(q.r!=p.r) return q.r<p.r;    return q.tim<p.tim;}bool cmp2(QUERY q,QUERY p){    return q.id<p.id;}void update(int to,int w){    sum[to]+=w;    if(w==1 && sum[to]==1) tmp++;    if(w==-1 && !sum[to]) tmp--;}int main(){    scanf("%d%d",&n,&m);    siz=sqrt(n);    for(int i=1;i<=n;i++) scanf("%d",&col[i]),original[i]=col[i];    char c[2]; int l,r;    while(m--)    {        scanf("%s%d%d",c,&l,&r);        if(c[0]==‘Q‘)        {            ++tot;            e[tot].l=l; e[tot].r=r; e[tot].id=tot; e[tot].bl=(l-1)/siz+1;            e[tot].tim=now;        }        else ch[++now].after=r,ch[now].pos=l;    }    sort(e+1,e+tot+1,cmp1);    int L=1,R=0; now=0;    for(int i=1;i<=tot;i++)    {        while(now<e[i].tim)        {            now++;            ch[now].before=col[ch[now].pos];            if(ch[now].pos>=L&&ch[now].pos<=R) update(ch[now].before,-1),update(ch[now].after,1);            col[ch[now].pos]=ch[now].after;        }        while(now>e[i].tim)        {            if(ch[now].pos>=L&&ch[now].pos<=R) update(ch[now].after,-1),update(ch[now].before,1);            col[ch[now].pos]=ch[now].before;            now--;        }        while(L<e[i].l) update(col[L++],-1);        while(L>e[i].l) update(col[--L],1);        while(R<e[i].r) update(col[++R],1);        while(R>e[i].r) update(col[R--],-1);         e[i].ans=tmp;    }    sort(e+1,e+tot+1,cmp2);    for(int i=1;i<=tot;i++) printf("%d\n",e[i].ans);    return 0;}

 

bzoj 2120


联系
我们