2025-06-26 随笔

回滚莫队

惭愧，我现在才开始学这么基础的东西。

众所周知，普通莫队之所以强悍，是因为它只需要加一个元素和删一个元素，就可以做到 $O(n\sqrt{n})$ 的优秀时间复杂度。但是存在很多问题不能同时做到加和删，那么就需要回滚莫队。

考虑下面一个问题：

P5906 【模板】回滚莫队&不删除莫队：给定一个长度为 $n$ 的序列，$q$ 次询问，每次询问给出区间 $[l,r]$，询问区间内两个相同数字的最大距离。

$1\le n,q\le 2\times 10^5$。

注意到该问题添加一个元素是十分容易的，预先对序列离散化后用两个桶就可以维护，但是删除一个元素如果删除到了答案，那么就不知道新的答案是什么（当然借助值域分块其实可以做到，不过在此不表），因此我们引入了回滚莫队。

回滚莫队强化了“莫队的本质是分块”这一思想，考虑显式地对原序列进行分块，然后将所有询问按照左端点的块编号为第一关键字，右端点为第二关键字排序，然后枚举每一个询问：

• 如果两端点都在同一块内，那么区间长度至多为 $O(\sqrt{n})$，暴力即可（记得清空）。
• 如果左端点所在块和之前左端点的所在块不同，那么就将已经存储的信息全部清空，然后将右指针 $R$ 移动到该块右端点 $r$，左指针移动到 $r+1$，形成了一个空区间，继续下面的操作。
• 如果询问区间的右端点与当前 $R$ 不同，就将 $R$ 移动到询问区间的右端点，并处理新增的元素。由于我们左端点在同一个块的询问都是按照右端点排序的，所以 $R$ 只会向右移动，而不会减少，符合不删的要求。
• 如果询问区间的左端点与当前 $L$ 不同，就将 $L$ 移动到询问区间的左端点，并处理新增的元素。由于初始时 $L=r+1$，所以 $L$ 只会向左移动，符合不删的要求。但是回答完一次询问后，之后的 $L$ 可能是乱序的，所以必须撤销这一部分新增的所有元素的信息（即所谓“回滚”），以将 $L$ 移动回 $r+1$ 来准备下一次询问。

可以证明，这样的复杂度是 $O(n\sqrt{n})$ 的（钦定 $n,q$ 同阶），代码大概就长这样：

std::sort(q + 1, q + m + 1, [](query a, query b){ // 排序
    return bel[a.l] != bel[b.l] ? bel[a.l] < bel[b.l] : a.r < b.r;
});
int L = 1, R = 0, blk = 0;
for(int i=1;i<=m;i++){
    if(bel[q[i].l] == bel[q[i].r]){
        // 在这里暴力回答询问，并清空暴力中维护的数据
        continue;
    }
    if(bel[q[i].l] != blk){
        while(top) his[top--].apply(); // 清空所有数据，即撤销所有操作
        R = br[bel[q[i].l]], L = R + 1, blk = bel[q[i].l];
    }
    while(R < q[i].r) add(++R); // 移动右指针，并处理新增的元素
    int lvl = top; // 保存一下左指针移动前的状态编号
    while(L > q[i].l) add(--L); // 移动左指针，并处理新增的元素
    // 这里你需要回答询问
    while(top > lvl) his[top--].apply(); // 撤销移动左指针更改的数据
    L = br[bel[q[i].l]] + 1; // 将左指针移回初始位置
}

Dirichlet 前缀和

经典问题：

给定一个长度为 $n$ 的序列 $a$，求序列 $b$ 满足：

$$b_m=\sum_{i\mid m} a_i$$

$1\leq n\leq 2\times 10^7$。

如果暴力做时间复杂度是 $O(n\log n)$ 的，难以通过本题。

考虑借助高维前缀和（Sum over Subsets DP）的思想，我们将每一个质因子一个一个加入，换句话说，令 $f(i,j)$ 表示考虑到前 $j$ 个质因子，$i$ 的所有因数 $j$ 的 $a_{\frac{i}{j}}$ 之和，那么这个只需要枚举 $j$，然后枚举 $i$ 就可以 $O(1)$ 转移（$f(i,j)=f(i,j-1)+f(\frac{i}{p_j},j)$），当然这个 dp 也是可以滚动数组的。由于该过程和埃式筛类似，所以时间复杂度也是 $O(n\log\log n)$ 可以通过本题。

for(int i=1;i<=tot;i++){
    for(int j=1;j*p[i]<=n;j++) f[j * p[i]] += f[j];
}