离线算法 莫队算法进阶
前算是把之前的坑填一填吧。这篇文章主要包含带修莫队，二维莫队等莫队算法的进阶应用，观看前请确保您已经熟练掌握了基本的莫队算法，不会的可以戳这里。
带修莫队
众所周知，普通莫队是不支持修改的，因为我们为了得到更优的时间复杂度，需要将每次询问离线下来，打乱顺序。
不过我们也可以通过加上一维时间维强行让它支持修改，这里的时间维在题目意义上就是需要进行的修改次数。
主要思想
原本我们的转移只有四种，以当前为 \(\left\) 为例，我们可以 \(\mathcal{O(1)}\) 扩展到：
[*]\(\left\)
[*]\(\left\)
[*]\(\left\)
[*]\(\left\)
若添加上一维时间，那么我们需要进行六种转移：
[*]\(\left\)
[*]\(\left\)
[*]\(\left\)
[*]\(\left\)
[*]\(\left\)
[*]\(\left\)
只是多了种转移方式，并不影响我们转移的复杂度。
离线询问排序的原则，以左端点所在块为第一关键字，右端点所在块为第二关键字，时间为第三关键字升序排列。
块长选定与时间复杂度
块长方面，通常取 \(\mathcal{n^{\frac{2}{3}}}\)，最终复杂度为 \(\mathcal{O(n^{\frac{5}{3}})}\)。
关于最优块长的分析：
摘自 OI-wiki。
实现
以 P1903 数颜色/ 维护队列 为例。
带修莫队板子题，思路同上，这里主要讲一下两个时间维的转移。
思路很简单，当查询到某次询问 \(q\) 时，若当前时间小于该次时间，则进行转移。若某次更改的点恰好在当前区间范围内，则进行更改操作，更改操作可以视为一次删除和一次添加，操作完成后为了方便之后再回退回去，我们交换删除的元素和更新的元素。
操作分离：
for(int i=1;i<=m;i++)
{
char op;int x,y;
cin>>op>>x>>y;
if(op=='Q')
q[++qcnt].id=qcnt,q.time=rcnt,
q.x=x,q.y=y;
else
r[++rcnt].p=x,r.x=y;
}转移部分：
void add(int x){ if(!mp) anss++; mp++;}void del(int x){ mp--; if(!mp) anss--;}int main(){ /*code*/ int L=1,R=0,tim=0; for(int i=1;iq.x) add(a[--L]); while(R
页:
[1]