离线算法 莫队算法进阶

前算是把之前的坑填一填吧。
这篇文章主要包含带修莫队，二维莫队等莫队算法的进阶应用，观看前请确保您已经熟练掌握了基本的莫队算法，不会的可以戳这里。
带修莫队

众所周知，普通莫队是不支持修改的，因为我们为了得到更优的时间复杂度，需要将每次询问离线下来，打乱顺序。
不过我们也可以通过加上一维时间维强行让它支持修改，这里的时间维在题目意义上就是需要进行的修改次数。
主要思想

原本我们的转移只有四种，以当前为 \(\left[l,r\right]\) 为例，我们可以 \(\mathcal{O(1)}\) 扩展到：

• \(\left[l-1,r\right]\)
  
• \(\left[l+1,r\right]\)
  
• \(\left[l,r-1\right]\)
  
• \(\left[l,r+1\right]\)
  

若添加上一维时间，那么我们需要进行六种转移：

• \(\left[l-1,r,time\right]\)
  
• \(\left[l+1,r,time\right]\)
  
• \(\left[l,r-1,time\right]\)
  
• \(\left[l,r+1,time\right]\)
  
• \(\left[l,r,time-1\right]\)
  
• \(\left[l,r,time+1\right]\)
  

只是多了种转移方式，并不影响我们转移的复杂度。
离线询问排序的原则，以左端点所在块为第一关键字，右端点所在块为第二关键字，时间为第三关键字升序排列。
块长选定与时间复杂度

块长方面，通常取 \(\mathcal{n^{\frac{2}{3}}}\)，最终复杂度为 \(\mathcal{O(n^{\frac{5}{3}})}\)。
关于最优块长的分析：

摘自 OI-wiki。
实现

以 P1903 数颜色/ 维护队列 为例。
带修莫队板子题，思路同上，这里主要讲一下两个时间维的转移。
思路很简单，当查询到某次询问 \(q\) 时，若当前时间小于该次时间，则进行转移。若某次更改的点恰好在当前区间范围内，则进行更改操作，更改操作可以视为一次删除和一次添加，操作完成后为了方便之后再回退回去，我们交换删除的元素和更新的元素。
操作分离：

1. for(int i=1;i<=m;i++)
2. {
3.         char op;int x,y;
4.         cin>>op>>x>>y;
5.         if(op=='Q')
6.                 q[++qcnt].id=qcnt,q[qcnt].time=rcnt,
7.                 q[qcnt].x=x,q[qcnt].y=y;
8.         else
9.                 r[++rcnt].p=x,r[rcnt].x=y;
10. }

复制代码

转移部分：
[code]void add(int x){        if(!mp[x]) anss++;        mp[x]++;}void del(int x){        mp[x]--;        if(!mp[x]) anss--;}int main(){        /*code*/        int L=1,R=0,tim=0;        for(int i=1;iq.x) add(a[--L]);                while(R