[toggle hide="yes" title="题目" color=""]
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。
[/toggle]
带修改的莫队,在普通莫队的基础上增加了在时间轴上的滚动,将询问和修改分别记录,保存每个询问的左右端点,以及在当前询问之前进行了多少次修改,将块长设置为n^(2/3),保证理论时间复杂度是O(n^(5/3)),再将询问按照(左端点所在块,右端点所在块,时间),进行三元组排序,可以感性理解一下查询区间移动的趋势,就能知道这样做的优势了,比较严谨的推导在这里:https://blog.sengxian.com/algorithms/mo-s-algorithm
对于这道题,我的做法是先将莫队的初始区间拉到(1,n),也就是序列的初始状态,预处理每个修改操作修改前的值,方便以后撤销修改,之后再进行莫队的操作,比较水(个人不是非常喜欢把修改操作全写成函数,感觉边界处理不如分别搞直观易调试)。
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 84 85 86 87 88 |
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <math.h> using namespace std; #define mxn 10005 inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar(); return s*f; } struct query{int p,v,o;}c[mxn]; struct query2{int l,r,t,id;}q[mxn]; int n,m,sc,sq,len,id[mxn],s[mxn],ans[mxn],tmp[mxn],cnt[mxn*100],cur; inline int gchar(){ char op=' '; while(op!='Q'&&op!='R') op=getchar(); if(op=='Q') return 0; return 1; } inline bool cmp(query2 a,query2 b){ if(id[a.l]==id[b.l]){ if(id[a.r]==id[b.r]) return a.t<b.t; else return id[a.r]<id[b.r]; } return id[a.l]<id[b.l]; } int main(){ // freopen("bzoj2120.in","r",stdin); // freopen("my.out","w",stdout); n=read(),m=read(),len=ceil(pow(n,0.67)); for(int i=1;i<=n;++i) { tmp[i]=s[i]=read(),id[i]=(i-1)/len+1; if(!cnt[s[i]]) cur++; cnt[s[i]]++; } for(int i=1;i<=m;++i){ int op=gchar(); if(!op) q[++sq].l=read(),q[sq].r=read(),q[sq].t=sc,q[sq].id=sq; else c[++sc].p=read(),c[sc].v=read(); } for(int i=1;i<=sc;++i) c[i].o=tmp[c[i].p],tmp[c[i].p]=c[i].v; sort(q+1,q+1+sq,cmp); for(int i=1,l=1,r=n,t=0;i<=sq;++i) { while(t<q[i].t) { t++; if(c[t].p>=l&&c[t].p<=r){ if(!cnt[c[t].v]) cur++; cnt[c[t].o]--,cnt[c[t].v]++; if(!cnt[c[t].o]) cur--; } s[c[t].p]=c[t].v; } while(t>q[i].t) { if(c[t].p>=l&&c[t].p<=r){ if(!cnt[c[t].o]) cur++; cnt[c[t].v]--,cnt[c[t].o]++; if(!cnt[c[t].v]) cur--; } s[c[t].p]=c[t].o; t--; } while(l<q[i].l) { cnt[s[l]]--; if(!cnt[s[l]]) cur--; l++; } while(l>q[i].l) { l--; if(!cnt[s[l]]) cur++; cnt[s[l]]++; } while(r<q[i].r) { r++; if(!cnt[s[r]]) cur++; cnt[s[r]]++; } while(r>q[i].r) { cnt[s[r]]--; if(!cnt[s[r]]) cur--; r--; } ans[q[i].id]=cur; } for(int i=1;i<=sq;++i) printf("%d\n",ans[i]); } |
叨叨几句... NOTHING