「BZOJ2120」数颜色
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
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
4
3
4
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
题解
同2453维护队列
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define N 10001 #define M 1000001 using namespace std; int n,q,m,block; int c[N],pos[N],pre[N],b[N],last[M]; int find(int x,int v) { int l=(x-1)*block+1,r=min(x*block,n); int first=l; while(l<=r) { int mid=(l+r)>>1; if(pre[mid]<v)l=mid+1; else r=mid-1; } return l-first; } void reset(int x) { int l=(x-1)*block+1,r=min(x*block,n); for(int i=l;i<=r;i++)pre[i]=b[i]; sort(pre+l,pre+r+1); } void build() { for(int i=1;i<=n;i++) { b[i]=last[c[i]]; last[c[i]]=i; pos[i]=(i-1)/block+1; } for(int i=1;i<=m;i++)reset(i); } int ask(int l,int r) { int ans=0; if(pos[l]==pos[r]) { for(int i=l;i<=r;i++)if(b[i]<l)ans++; } else { for(int i=l;i<=block*pos[l];i++)if(b[i]<l)ans++; for(int i=block*(pos[r]-1)+1;i<=r;i++)if(b[i]<l)ans++; } for(int i=pos[l]+1;i<pos[r];i++) ans+=find(i,l); return ans; } void change(int x,int v) { for(int i=1;i<=n;i++)last[c[i]]=0; c[x]=v; for(int i=1;i<=n;i++) { int t=b[i]; b[i]=last[c[i]]; if(t!=b[i])reset(pos[i]); last[c[i]]=i; } } int main() { scanf("%d%d",&n,&q); for(int i=1;i<=n;i++)scanf("%d",&c[i]); block=int(sqrt(n)+log(2*n)/log(2)); if(n%block)m=n/block+1; else m=n/block; build(); char ch[5];int x,y; for(int i=1;i<=q;i++) { scanf("%s%d%d",ch,&x,&y); if(ch[0]=='Q')printf("%d\n",ask(x,y)); else change(x,y); } return 0; } |
计数器 9774813
OI 课件=>
OI 课件=>
修改的时间复杂度，nlogn？