首页 > 代码库 > BZOJ 2120 数颜色&2453 维护队列 [带修改的莫队算法]【学习笔记】
BZOJ 2120 数颜色&2453 维护队列 [带修改的莫队算法]【学习笔记】
2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MBSubmit: 3665 Solved: 1422
[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
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
Sample Output
4
3
4
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
2016.3.2新加数据两组by Nano_Ape
参考资料：
1.http://blog.csdn.net/a_crazy_czy/article/details/51544720
2.http://blog.csdn.net/WerKeyTom_FTD/article/details/51540342
序列分块
对于询问操作，根据左边界所在块为第一关键字，右边界所在块为第二关键字，上一个修改操作的“时间”为第三关键字排序
维护当前区间l,r和修改操作到的时间now
移动now就是把一个数outm然后另一个数inm，注意是进行这个修改还是撤销这个修改
移动l和r和普通莫队算法一样了
对于本题cnt[x]表示在当前区间x出现的次数
转移显然是O(1)的，只要加减即可
还有一个问题，从复杂度分析来看：
分块大小S为n2/3，那么我们就有n1/3块。
原本的莫队关键字只有两个，一个是左边界，一个是右边界。而带修改莫队要再加上一维：在第几个操作之后。
我们按照这左边界所在块、右边界所在块以及第三关键字排序（上面说的那个）。
统计答案时多维护一个指针记录修改操作执行到哪里，移动时直接修改即可，如果在区间内还要计算其对答案的影响。
左指针移动次数：O(n×n2/3)=O(n5/3)。
右指针移动次数：O(n×n2/3+n1/3×n)=O(n5/3)。
修改指针移动：O((n1/3)2×n)=O(n5/3)。
因此总时间复杂度O(n5/3)。
应该是按n2/3分块，然而用n1/2分块比他快了几十ms.......................
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e4+5,M=1e2+5,S=1e6+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,x,y,bl,c[N],last[N],pos[N];//last[x] x位置更改之前的颜色 char s[10];int t1,t2;struct data1{ int l,r,id,tme; ll a,b; bool operator <(const data1 &x)const{ if(pos[l]==pos[x.l]){ if(pos[r]==pos[x.r]) return tme<x.tme; else return pos[r]<pos[x.r]; }else return pos[l]<pos[x.l]; }}q[N];struct data2{ int x,d,pre;}p[N];int cnt[S];int l=1,r,now,ans,a[N];//inline void outm(int x){// cnt[x]--;// if(cnt[x]==0) ans--;//}inline void outm(int x){ ans-=(--cnt[x])==0;}inline void inm(int x){ ans+=(++cnt[x])==1;}//inline void inm(int x){// cnt[x]++;// if(cnt[x]==1) ans++;//}inline void change(int x,int d){ if(l<=x&&x<=r){ outm(c[x]); inm(d); } c[x]=d;}int main(){ n=read();m=read(); bl=sqrt(n); for(int i=1;i<=n;i++) c[i]=last[i]=read(),pos[i]=(i-1)/bl+1; for(int i=1;i<=m;i++){ scanf("%s",s);x=read();y=read(); if(s[0]==‘Q‘) q[++t1].l=x,q[t1].r=y,q[t1].id=t1,q[t1].tme=t2; else p[++t2].x=x,p[t2].d=y,p[t2].pre=last[x],last[x]=y; } sort(q+1,q+1+t1); for(int i=1;i<=t1;i++){ while(now<q[i].tme){ now++; change(p[now].x,p[now].d); } while(now>q[i].tme){ change(p[now].x,p[now].pre); now--; } while(l<q[i].l){ outm(c[l]);l++; } while(l>q[i].l){ l--;inm(c[l]); } while(r<q[i].r){ r++;inm(c[r]); } while(r>q[i].r){ outm(c[r]);r--; } a[q[i].id]=ans; } for(int i=1;i<=t1;i++) printf("%d\n",a[i]);}
BZOJ 2120 数颜色&2453 维护队列 [带修改的莫队算法]【学习笔记】