[Hard] CF2043G Problem with Queries

xiezheyuan2025/1/31约 1942 字大约 10 分钟

在考场上较为实用的在线带修莫队 $O((n+m)n^{2/3})$ 做法。

简要题意

给定一个长度为 $n$ 的序列 $a$ ，有 $m$ 次操作，支持：

1 p v 令 $a_p\gets v$ 。
2 l r 计算有多少个数对 $(i,j)$ 满足 $l\leq i\lt j\leq r$ 且 $a_i\neq a_j$ 。

强制在线， $1\leq n\leq 10^5,1\leq m\leq 3\times 10^3,1\leq a_i\leq n$ 。

时间限制 $8000\mathrm{ms}$ ，空间限制 $1024\mathrm{MiB}$ 。

思路

Part 1

对于询问，令 $L=r-l+1$ ，则共有 $\frac{1}{2}(L^2-L)$ 个数对 $(i,j)$ 满足 $l\leq i\leq j\leq r$ 。假如计算出每种数的出现次数平方和 $k$ ，则就有 $\frac{k-L}{2}$ 个不满足题目要求的数对，两式相减，得到 $\frac{1}{2}(L^2-k)$ 。

$L$ 计算是容易的，所以问题是计算 $k$ ，也就是区间每种数出现次数的平方和。

如果允许离线、没有修改，则为 P2709 小 B 的询问一题，可以直接用普通莫队算法解决。
如果允许离线，存在修改，则可以将普通莫队改为带修莫队，做法可以参考 P1903 [国家集训队] 数颜色 / 维护队列。

现在本题要求强制在线，导致我们难以使用一般的莫队算法解决，这时难道我们需要写正经的分块吗？不，我们考虑莫队的在线化改造。

Part 2

先来思考普通莫队算法的在线化改造。

将序列分为 $B$ 块，在询问的时候，从若干个整块组成的区间出发，套用莫队双指针移动到询问区间，从而找到询问区间的答案，这就需要我们预处理以下信息：

所有整块区间的答案。这需要 $O(nB)$ 的时间复杂度与空间复杂度。
所有整块区间的莫队中间状态，在本题中，就是记录每个数出现次数的桶。如果全部记录下来，无论时空复杂度都是 $O(nB^2)$ 难以承受。不过这个出现次数的信息显然是可以差分的，因此可以改为记录若干个整块组成的前缀的出现次数，时空复杂度降为 $O(nB)$ 。

注意在双指针移动时，我们需要用一个桶来维护指针移动时出现次数信息的变化量，这个桶和初始整块区间信息加起来，作为真正的出现次数信息。这个桶的清空显然不能暴力清空，可以用栈记录修改过的位置。

于是时间复杂度为 $O(nB+m\cdot \frac{n}{B})$ ，根据均值不等式，取 $B=\sqrt{m}$ 时时间复杂度最优，为 $O(n\sqrt{m})$ ，该时间复杂度与普通莫队算法相同。

Part 3

现在思考带修莫队算法的在线化改造。

这时难点主要在于在每次修改时，会影响到 $O(B^2)$ 个区间的答案，如果继续取 $B=\sqrt{m}$ 是难以承受的，不妨考虑带修莫队的思路，遇到修改先不真的更改，而是记录下来，等到后面在应用 / 撤销修改。

具体地，我们遇到修改时，先修改莫队中间状态（出现次数桶），然后在询问的时候考虑应用修改。

如何应用修改呢？貌似只能暴力了，那我们不妨真的暴力，记录一下每个若干个整块构成的区间上次更新的时间戳，然后将这个区间的答案更新到当前时间戳。

具体实现的话，由于桶已经是最新的了，所以更新答案必须倒着更新，用一个辅助桶来表示这次修改前的出现次数桶，然后计算答案。

接下来就是和 Part 2 一样的过程了。

分析一下复杂度，预处理同样是 $O(nB)$ ，单个询问不好考虑，考虑最多 $m$ 个修改，可以依次作用在 $B^2$ 个块中，故询问部分总时间复杂度为 $O(mB^2)$ ，修改部分总时间复杂度为 $O(m\cdot \frac{n}{B})$ 。

故总时间复杂度为 $O(nB+mB^2+m\cdot\frac{n}{B})$ ，通过平衡阶数法，取 $B=O(n^{1/3})$ 达到最优时间复杂度 $O(n^{4/3}+mn^{2/3})$ ，和带修莫队算法的时间复杂度相同。

Part 4

我们需要卡常。

经过实践，取块长 $\frac{n}{B}=2300$ 表现较为平衡。另外，需要加入额外的判断，来让莫队时选取的若干个整块构成的初始区间最优，可以通过分类讨论左右端点来得到，具体可以看代码实现。

其他就没有什么非常厉害的卡常了，正常关闭同步流 + 火车头即可。

根据 OI Wiki 的线索，我们也许可以做一个伪在线，由于操作编号没有加密，通过求出操作的分布情况来调整超参数 $B$ ，这一点我没有实现，如果有同学实现了并取得了较好的成效，请私信我。

代码

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "inline", "-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;

const int N = 1e5 + 5, BK = 55, M = 3e5 + 5, K = 1e7 + 5;
using i64 = long long;
int n, m, a[N], cnt[BK][N], tim[BK][BK];
i64 ans[BK][BK];
int bl[BK], br[BK], bel[N];

struct tracer{
    int a[N];
    int vp[K], tot;
    int operator[](int x){ return a[x]; }
    void set(int pos, int x){ vp[++tot] = pos, a[pos] = x; }
    void add(int pos, int x = 1){ set(pos, a[pos] + x); }
    void roll(){ while(tot) a[vp[tot--]] = 0; }
} bkt;

void init(){
    int blk = max((int)pow(n, 2.0 / 3), 1);
    if(n > 5e4) blk = 2300;
    for(int i=1;i<=n/blk;i++) bl[i] = (i - 1) * blk + 1, br[i] = i * blk;
    br[n / blk] = n;
    for(int i=1;i<=n/blk;i++){
        for(int j=bl[i];j<=br[i];j++) bel[j] = i, bkt.add(a[j]);
        for(int j=1;j<=n;j++) cnt[i][j] = bkt[j];
    }
    for(int i=1;i<=bel[n];i++){
        bkt.roll();
        for(int j=i;j<=bel[n];j++){
            ans[i][j] = ans[i][j - 1];
            for(int k=bl[j];k<=br[j];k++){
                ans[i][j] += bkt[a[k]] << 1 | 1;
                bkt.add(a[k]);
            }
        }
    }
}

struct update_option{
    int pos, lst, val;
} upd[M];
int updt;

void update(int x, int y){
    if(a[x] == y) return;
    upd[++updt] = {x, a[x], y};
    for(int i=bel[x];i<=bel[n];i++) cnt[i][a[x]]--, cnt[i][y]++;
    a[x] = y;
}

int get(int l, int r, int p){ return cnt[r][p] - cnt[l - 1][p]; }

i64 ret;

void add(int p, int L, int R){
    ret += (bkt[p] + get(L, R, p)) << 1 | 1;
    bkt.add(p);
}

void del(int p, int L, int R){
    ret -= ((bkt[p] + get(L, R, p)) << 1) - 1;
    bkt.add(p, -1);
}

i64 query(int l, int r){
    int L = bl[bel[l]], R = br[bel[r]];
    int sl = bel[l], sr = bel[r];
    if(bel[l] != bel[n]){
        if(bl[bel[l] + 1] - l < l - bl[bel[l]]) sl = bel[l] + 1, L = bl[sl];
    }
    if(bel[r] != bel[1]){
        if(r - br[bel[r] - 1] < br[bel[r]] - r){
            if(sl <= (bel[r] - 1)) sr = bel[r] - 1, R = br[sr];
        }
    }
    bkt.roll();
    for(int i=updt;i>tim[sl][sr];i--){
        auto [pos, lst, val] = upd[i];
        if(pos < L || pos > R) continue;
        bkt.add(lst), bkt.add(val, -1);
        ans[sl][sr] -= ((get(sl, sr, lst) + bkt[lst]) << 1) - 1;
        ans[sl][sr] += (get(sl, sr, val) + bkt[val]) << 1 | 1;
    }
    tim[sl][sr] = updt;
    bkt.roll();
    ret = ans[sl][sr];
    while(L > l) add(a[--L], sl, sr);
    while(R < r) add(a[++R], sl, sr);
    while(L < l) del(a[L++], sl, sr);
    while(R > r) del(a[R--], sl, sr);
    return ret;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    init(); i64 lastans = 0;
    cin >> m;
    // cerr << (1.0 * clock() / CLOCKS_PER_SEC) << ' ' << n << ' ' << m << '\n';
    while(m--){
        int op, x, y; cin >> op >> x >> y;
        x = (x + lastans) % n + 1;
        y = (y + lastans) % n + 1;
        if(op == 1) update(x, y);
        else{
            if(x > y) swap(x, y);
            i64 ret = query(x, y);
            cout << (lastans = ((1ll * (y - x + 1) * (y - x + 1) - ret) >> 1));
            cout << ' ';
            assert(lastans >= 0);
        }
        // if(m % 10000 == 0) cerr << m << ' ' << (1.0 * clock() / CLOCKS_PER_SEC) << '\n';
    }
    return 0;
}

// Written by xiezheyuan