带修莫队学习笔记 -1.参考资料 0.定义 1.算法
无
0.定义
无
1.算法
1.1 普通莫队
对左端点分块，然后把询问按照块的编号排序，相同块内按照右端点排序。
然后考虑两次询问之间转移的变化量，就是左端点移动+右端点移动，直接类似于 two pointers 即可。
可以证明取块长为 (O(sqrt n)) 时可以达到理论最优复杂度是 (O(nsqrt nf(n))) 的，其中 (f(n)) 是普通莫队的复杂度。
1.2 带修莫队
简单来说就是多了个时间轴的三维莫队。
考虑沿用普通莫队的想法，对左端点和右端点都分块，然后把询问按照先左端点块编号后右端点块编号排序，相同部分按照时间排序。
然后考虑两次询问之间转移的变化量，是左端点移动+右端点移动+时间的改变，同理上面操作即可。three pointers。
可以证明取块长为 (O((nq)^frac{1}{3})sim O(n^frac{2}{3})) 时可以达到理论最优复杂度是 (O(n^frac{4}{3}q^frac{1}{3})sim O(n^frac{5}{3}))，其中 (q) 表示修改个数，一般认为 (qsim n)。
1.3 例题
直接跑带修莫队即可。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=133335,M=1000005;
int n,m,a[N],cnt[M],bl,uv,cntr,cntq,ans[N];
char op[2];
struct query{
int id,l,r,t,posl,posr;
bool operator<(const query&x)const{
return posl<x.posl||posl==x.posl&&posr<x.posr||posl==x.posl&&posr==x.posr&&t<x.t;
}
}q[N];
int x[N],c[N];
void add(int x){if((cnt[x]++)==0)uv++;}
void del(int x){if((--cnt[x])==0)uv--;}
void upd(int id,int t){
if(q[id].l<=x[t]&&x[t]<=q[id].r)del(a[x[t]]),add(c[t]);
swap(a[x[t]],c[t]);
}
int main(){
scanf("%d%d",&n,&m);bl=pow(n,0.667);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
scanf("%s",op);
if(op[0]=='R')cntr++,scanf("%d%d",&x[cntr],&c[cntr]);
else {
cntq++;
scanf("%d%d",&q[cntq].l,&q[cntq].r);
q[cntq].id=cntq,q[cntq].t=cntr;
q[cntq].posl=q[cntq].l/bl,q[cntq].posr=q[cntq].r/bl;
}
}
sort(q+1,q+cntq+1);
for(int i=1,l=1,r=0,t=0;i<=cntq;i++){
while(l>q[i].l)add(a[--l]);
while(r<q[i].r)add(a[++r]);
while(l<q[i].l)del(a[l++]);
while(r>q[i].r)del(a[r--]);
while(t<q[i].t)upd(i,++t);
while(t>q[i].t)upd(i,t--);
ans[q[i].id]=uv;
}
for(int i=1;i<=cntq;i++)printf("%d
",ans[i]);
return 0;
}