简单分块与莫队

· · 个人记录

1 - 分块

1.1 - 定义

分块是将要维护的信息分成若干块，而后通过维护整块的信息或者是块间的信息来优化算法。

1.2 - 序列分块

在序列上以线段树来类比，线段树是将序列每次对半分，最后得到一个比较完美的二叉树的结构。分块是将序列首先分成一个多叉树，根的儿子节点的儿子就直接是叶子。

1.3 - 复杂度分析

复杂度分析：假设块的大小是 B，一共有 \frac nB 块，整块部分的复杂的度就是 O\left(\frac nB\right)，散块部分的复杂度是 O(B)，所以整体复杂度是 O\left(\frac nB+B\right)，显然 B 取 \sqrt n 的时候最优。

分块的时候务必分析时间复杂度来取合适的块大小，不要无脑取根号。

1.4 - 分块的优点

分块在修改的时候，只有若干整块以及两个散块需要修改，在整块的处理上，其和线段树等一样，都是打标记，但是在散块上，其只需要暴力修改两个小散块的信息，整个修改过程只和散块中的元素有关，而线段树等数据结构会从叶子开始一层层往上更新，最后牵扯到整个序列信息。

分块在统计答案的时候只有整块的散块的区别，不像线段树等那般有多层结构，这使得信息难以合并的时候，分块有其特殊的用处。

1.5 - 分块思想的另一种应用

对于动态修改问题，有时候我们会遇到这样一种情况：想到了两种做法，一种可以快速修改，但查询很慢；一种可以快速查询，但是修改很慢。这种时候也可以使用分块算法进行折中处理。

2 - 莫队

2.1 - 普通莫队

对于序列上的区间询问问题，如果从 [l,r] 的答案能够 O(1)扩展到 [l-1,r],[l+1,r],[l,r+1],[l,r-1] 的答案，那么可以在 O(n\sqrt n) 的复杂度内求出所有询可的答案，实际就是一种优美的暴力。

2.1.1 - 实现

离线后排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间的答案。

2.1.2 - 排序方法

令块长为 B，按照 \left(\left\lfloor\frac lB\right\rfloor,r\right) 二元组升序排序，其中第一关键字是块的编号，第二关键字是右端点。

2.1.3 - 复杂度分析

设序列长度为 n，询问个数为 m。 可以发现从 \left(l_{1}, r_{1}\right) 转移到 \left(l_{2}, r_{2}\right) 的代价为他们之间的曼哈顿距离。对于每一个询问序列中的每一个块（第一关键字相同)，整个块内纵坐标最多变化 n 长度 (纵坐标必然单调不减)，对于每个询问，横坐标最多变化 S。一共有 \frac{n}{S} 个块，相邻块之间转移的复杂度为 O(n)，所以复杂度为 O\left(\frac{n^{2}}{B}+m B+\frac{n^{2}}{B}\right) 不妨让 n, m 同阶，取 S=\sqrt{n} 时可达到最优复杂度 O(n \sqrt{n})。

2.2 - 带修莫队

对于某些允许离线的带修改区间查询来说，我们能够对莫队算法做出一些修改，使得他支持带修改的区间查询。做法就是把莫队直接加上一维，变为带修莫队。 对于具体实现方法，我们把修改操作编号称为" 时间戳"，而查询操作的时间䧸沿用之前最近的修改操作的时间䧸。跑主算法时定义当前时间戳为 t ，对于每个查询操作，如果当前时间䧸相对太大了，说明已进行的修改操作比要求的多，就把之前改的改回来，反之往后改。只有当当前区间和查询区间左右端点、时间戳均重合时，才认定区间完全重合，此时的答案才是本次查询的最终答案。

2.2.1 - 实现

本质上就是查询的时候，信息在区间 [l,r] 上多加了一维 t，代表当前的时间戳。

例题 P1903。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+3;
int sum,n,m,sqn,cntq,cntm;
int cnt[maxn],a[maxn],ans[maxn];
struct ovo{
    int l, r, tim, id;
    bool operator < (const ovo &owo) const{
        if(l / sqn != owo.l / sqn) return l / sqn < owo.l / sqn;
        if(r / sqn != owo.r / sqn) return r / sqn < owo.r / sqn;
        return tim < owo.tim;
    }
}pos[maxn];
struct{ int pos, val; }meg[maxn];
void add(int x){ sum += ++cnt[x] == 1; }
void del(int x){ sum -= --cnt[x] == 0; }
void rep(int x, int sta){ 
    if(pos[sta].l <= meg[x].pos && meg[x].pos <= pos[sta].r) 
        del(a[meg[x].pos]), add(meg[x].val); 
    swap(meg[x].val,a[meg[x].pos]); 
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sqn=pow(1.0*n,2.0/3);
    for(int i=1;i<=m;i++){
        char c;
        cin>>c;
        if(c=='Q') cntq++, cin>>pos[cntq].l>>pos[cntq].r, pos[cntq].id=cntq, pos[cntq].tim=cntm;
        else cntm++, cin>>meg[cntm].pos>>meg[cntm].val;
    }
    sort(pos+1,pos+cntq+1);
    for(int i=1,l=0,r=0,c=0;i<=cntq;i++){
        while(l<pos[i].l) del(a[l++]);
        while(r<pos[i].r) add(a[++r]);
        while(l>pos[i].l) add(a[--l]);
        while(r>pos[i].r) del(a[r--]);
        while(c<pos[i].tim)rep(++c,i);
        while(c>pos[i].tim)rep(c--,i);
        ans[pos[i].id]=sum;
    }
    for(int i=1;i<=cntq;i++) cout<<ans[i]<<'\n';
    return 0;
}

2.2.2 - 复杂度分析

设块大小为 B ，序列长 n ，查询数 q 。

考虑第三维的移动次数，前两维分出的块个数是 \left(\frac{n}{B}\right)^{2} ，第三维的移动范围是 n ，所以是 \frac{n^{3}}{B^{2}} 。

第一维的移动次数显然 q B 。

如果不考虑第二维的移动次数， q, n 同阶的话，复杂度是 O\left(\frac{n^{3}}{B^{2}}+n B\right) ， B=n^{\frac{2}{3}} 理论最优。

第二维的移动次数比较难分析，但是从最坏的角度来看，考虑第一维，第二维总是要遍历完整个序列，移动 \frac{n}{B} \times n ，于此同时，第三维的修改使得第二维在块内移动 q B 。不难发现这个最坏的复杂度也不会影响到 B 的选择。

2.3 - 树上莫队

把序列问题放到了树上。

欧拉序 \text{(dfn)}：
欧拉序是在 dfs 的时候，在进节点的时候把节点加入序列，出节点的时候也把节点加入序列后得到的序列。

2.3.1 - 实现

算法核心是使用树的欧拉序使得树上问题变成序列问题。

欧拉序上，刚好把链上每个点标记一遍，不在链上的点标记 0 遍或 2 遍，虽然 LCA 并不在这段区间内，但是只有这一个点，就很好处理了。

转化之后树上问题变成了序列问题，使用普通莫队即可。

类似的，树上也有带修莫队，也是把树上问题变成序列后跑带修莫队。

2.4 - 回滚莫队

普通莫队无法快速解决最值 \text{(min-max)} 问题。

以下以 \max 举例。

2.4.1 - 实现

要维护最大值，显然只能加数不能减数。所以考虑使用回滚莫队。

对于左右端点在同一块内，暴力。

剩下的按照普通的莫队排序，现在考虑左端点在同一块内的查询。其思路如下。

假设 A 和 B 是这次查询的左右端点，C 和 D 是下次的查询的，L 和 R 是当前的左右端点，竖线区分开了当前块与块外面的部分。

--A--L|R---B---- 左端点设为所在块的右端点；
--A--L|----R---- 扩展右端点；
--L---|----R---- 右端点到达目标点后，扩展左端点；
此时我们得到了当前查询的答案；
-----L|----R---- 左端点到达目标点后，撤回左端点的修改；
---C-L|----R---D 对下一个查询重复操作；
---C-L|--------R 扩展右端点；
……

2.4.2 - 复杂度分析

这样看，整个过程只有左右端点的扩展和左端点修改的撤回，就不存在删除操作了。

和普通莫队相比，复杂度并没有发生什么变化，只是常数变大了。