时间戳

首页 > 技术文章 > bzoj 2120: 数颜色

bzoj 2120: 数颜色

Yuzao 2017-08-22 22:07 原文

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

 
题解:
数据水,直接暴力莫队即可,并且此题带修改,很容易想到可以直接加上对t指针的移动,t表示当前的时刻
我们记录每一个询问所在的时间,和修改的区间,每一次把时间调到当前询问所在时间,然后套正常莫队即可
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #define RG register
 8 #define il inline
 9 #define iter iterator
10 using namespace std;
11 const int N=1e6+5,M=1e4+5;
12 int a[M],n,m,rc=0,cnt=0,blg,L,R,c[N],tot=0,ans[M],last[M];
13 struct up{
14     int x,y,lst;
15 }r[M];
16 struct node{
17     int l,r,lb,t,id;
18 }q[M];
19 void upd(int x,int to){
20     if(L<=x && x<=R){
21         c[a[x]]--;if(c[a[x]]==0)tot--;
22         a[x]=to;c[to]++;if(c[to]==1)tot++;
23     }
24     else a[x]=to;
25 }
26 void add(int x){
27     c[a[x]]++;if(c[a[x]]==1)tot++;
28 }
29 void delet(int x){
30     c[a[x]]--;if(c[a[x]]==0)tot--;
31 }
32 bool comp(const node &pp,const node &qq){
33     if(pp.lb!=qq.lb)return pp.lb<qq.lb;
34     if(pp.r!=qq.r)return pp.r<qq.r;
35     return pp.t<qq.t;
36 }
37 void work()
38 {
39     char s[2];int x,y;
40     scanf("%d%d",&n,&m);blg=sqrt(n);
41     for(int i=1;i<=n;i++)scanf("%d",&a[i]),last[i]=a[i];
42     for(int i=1;i<=m;i++){
43         scanf("%s%d%d",s,&x,&y);
44         if(s[0]=='R'){
45             r[++rc].x=x;r[rc].y=y;r[rc].lst=last[x];
46             last[x]=y;
47         }
48         else{
49             q[++cnt].l=x;q[cnt].r=y;q[cnt].lb=q[cnt].l/blg;q[cnt].t=rc;
50             q[cnt].id=cnt;
51         }
52     }
53     sort(q+1,q+cnt+1,comp);
54     int t=0;L=1;R=0;
55     for(int i=1;i<=cnt;i++){
56         while(t>q[i].t){
57             upd(r[t].x,r[t].lst);t--;
58         }
59         while(t<q[i].t){
60             t++;upd(r[t].x,r[t].y);
61         }
62         while(R<q[i].r)R++,add(R);
63         while(L>q[i].l)L--,add(L);
64         while(R>q[i].r)delet(R),R--;
65         while(L<q[i].l)delet(L),L++;
66         ans[q[i].id]=tot;
67     }
68     for(int i=1;i<=cnt;i++)printf("%d\n",ans[i]);
69 }
70 
71 int main()
72 {
73     freopen("pp.in","r",stdin);
74     work();
75     return 0;
76 }

 

推荐阅读