首页 > 代码库 > BZOJ 2120 数颜色&2453 维护队列 [带修改的莫队算法]【学习笔记】
BZOJ 2120 数颜色&2453 维护队列 [带修改的莫队算法]【学习笔记】
题意：
询问区间中不同颜色的个数，单点修改颜色
发现以前写的学习笔记没法看，于是重写一下(不就是会用latex了嘛)
额外维护一个当前修改操作执行到的时间
如果要进行某个查询操作，修改操作的时间必须移动到这个查询操作处
按照$(pos[l], pos[r], tim)$排序
令$S=N^{\frac{2}{3}}$, 有$N^{\frac{1}{3}}$块
$l$移动$N*N^{\frac{2}{3}}$次
$r$移动$N*N^{\frac{1}{3}}+N*N^{\frac{2}{3}}$次
$cur$移动$N*N^{\frac{1}{3}}*N^{\frac{1}{3}}$次
注意排序一定排对了啊啊啊啊
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;typedef long long ll;const int N=1e4+5, M=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,Q,a[N],pos[N],m,block,t[N],x,y;char op[3];struct meow{ int l,r,tim,id; bool operator <(const meow &a) const{ return pos[l]==pos[a.l] ? ( pos[r]==pos[a.r] ? tim<a.tim : pos[r]<pos[a.r]) : pos[l]<pos[a.l]; }}q[N];struct cmeow{int p,v,last;}cq[N];int p,tim, ans[N];int c[M], now;int l=1,r=0,cur=0;inline void add(int x) {now+= (++c[x])==1;}inline void del(int x) {now-= (--c[x])==0;}inline void cha(int p,int v){ if(l<=p && p<=r) add(v), del(a[p]); a[p]=v;}void modui(){ for(int i=1;i<=p;i++){ while(cur<q[i].tim) cur++, cha(cq[cur].p, cq[cur].v); while(cur>q[i].tim) cha(cq[cur].p, cq[cur].last), cur--; while(r<q[i].r) r++, add(a[r]); while(r>q[i].r) del(a[r]), r--; while(l<q[i].l) del(a[l]), l++; while(l>q[i].l) l--, add(a[l]); ans[ q[i].id ]=now; }}int main(){ //freopen("in","r",stdin); n=read(); Q=read(); block=sqrt(n); m=(n-1)/block+1; for(int i=1;i<=n;i++) a[i]=t[i]=read(), pos[i]=(i-1)/block+1; for(int i=1;i<=Q;i++){ scanf("%s",op); x=read(); y=read(); if(op[0]==‘Q‘) q[++p]=(meow){x, y, tim, p}; else cq[++tim]=(cmeow){x, y, t[x]}, t[x]=y; } sort(q+1, q+1+p); modui(); for(int i=1;i<=p;i++) printf("%d\n",ans[i]);}
BZOJ 2120 数颜色&2453 维护队列 [带修改的莫队算法]【学习笔记】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。