简介
莫涛大神创造出的离线询问算法的带修改版。
算法基础:需要掌握莫队算法,会打暴搜(暴力)。
一个叫莫的双端队列。
只支持单点修改
操作方法
普通的不带修改的莫队算法要把每个询问带上两个关键字排序,现在待修改的莫队算法要带上三个关键字排序。
这也是主要思想,和普通的莫队一样很简单的思想。
原本的莫队是[l,r]向连边推,现在带修改那么就设设三元(l,r,x),x为已经操作了x次修改,可以向(l±1,r,x),(l,r±1,x),(l,r,x±1)推,原理一样。
初始操作
fo(i,1,m) {
scanf("%s%d%d",s,&k,&l);
if (s[0]=='Q')a[++tot].l=k,a[tot].r=l,a[tot].x=num,a[tot].p=tot;
else d[++num].x=k,d[num].o=gai[k],d[num].y=l,gai[k]=l;
}
代码中‘Q’是询问,否则是修改。
a是询问数组
a[tot]{
l:询问的左边——所在块为第一个关键字
r:询问的右边——第二个关键字
x:此次询问的上一个修改操作——第三个关键字
p:此次询问的序号——用于统计答案
}
d是修改数组
d[num]{
x:此次修改哪一个节点的值
y:修改为什么值
o:此次修改时原来的值——用于还原数组
}
排序
da=1300;
fo(i,1,n)scanf("%d",&b[i]),gai[i]=b[i],kuai[i]=(i-1)/da+1;
先定义每个块的大小,有时块大速度快,有时块小速度快。还要存每个节点在哪一个块。
bool cmp(node x,node y){
return kuai[x.l]<kuai[y.l]||kuai[x.l]==kuai[y.l]&&x.r<y.r||kuai[x.l]==kuai[y.l]&&x.r==y.r&&x.x<y.x;
}
排序条件
sort(a+1,a+tot+1,cmp);
对询问数组排序。
主程序——维护答案
l和r分别是上一次的操作区间左右端点在什么位置,now是上一个询问的上一个修改操作在d数组中的位置(及a[i-1].x)。
为了方便操作,初始值:l=1,r=0,now=0。
l=1;
fo(i,1,tot){
if (now<a[i].x)fo(j,now+1,a[i].x)change(d[j].x,d[j].y);
else fod(j,now,a[i].x+1)change(d[j].x,d[j].o);
if (l<a[i].l)fo(j,l,a[i].l-1)update(j);
else fo(j,a[i].l,l-1)update(j);
if (r<a[i].r)fo(j,r+1,a[i].r)update(j);
else fo(j,a[i].r+1,r)update(j);
ans1[a[i].p]=ans;
l=a[i].l;r=a[i].r;now=a[i].x;
}
对于当前的询问操作a[i],只有序号为a[i].x及其以前的修改操作才会影响到a[i]的询问。
如果now< a[i].x说明d[now+1到a[i].x]这些修改操作还没有进行,否则如果now>a[i].x说明d[a[i].x+1到now]这些修改操作多进行了——但是为什么是倒着做呢,因为后面的操作进行之后,不知道原来的值,要倒着逐个修改为d[j].o(此次修改上一个的值)才能还原成原来的值。
接下来就是普通莫队算法的正常操作。
但是正常的加入删除的update不是要打1或-1吗?
这里用了一个小技巧。
更新、修改值
bz数组是标记当前x节点是否进队(相当于上一次询问操作是否包含x节点)
void change(int x,int y){
if(bz[x]){
update(x);
b[x]=y;
update(x);
}
else b[x]=y;
}
如果要修改当前x的值y为的话,要分一分情况:1、如果bz[x]=1,那么就是在上一次询问操作中含有x节点,所以修改了x节点可能会影响答案,那么就update(x)一次让x出队,再修改x一次让x入队;2、如果x没有被上一次询问包含,那么修改了也不会影响答案,所以直接修改就好了。
update不明白的下面马上说。(联系上下文是个好方法~~)
void update(int x){
if(bz[x]){
shu[b[x]]--;
if(!shu[b[x]])ans--;
}
else{
shu[b[x]]++;
if(shu[b[x]]==1)ans++;
}
bz[x]^=1;
}
有些打法直接在update加个1和-1表示加入和删除就好了,但是这样打有点长。
但是用bz[x]表示x在上一次询问是否涉及到,那么要对已经入队的x进行update(x)操作就是要让它出队并更新答案;如果x在上一次询问中没有涉及到就是bz[x]=0,那么对x进行update(x)操作就相当于让x入队并对答案更新。
注意bz[x]进行update操作后要取反。
输出答案
fo(i,1,tot)printf("%d\n",ans1[i]);
题目
uva12345 Dynamic len
由于本人是个蒟蒻
对于莫队的修改的了解也就这么多。