题解：P3688 [ZJOI2017] 树状数组

· · 题解

洛谷 P3688 [ZJOI2017] 树状数组 题解

意外地抢到了最优解，考虑到本解法在统计答案方面相比其他大多数题解有创新，故分享出来供大家参考。

题意简述

给定一个实现错误的树状数组，和对 2 取模，其更新与查询部分相比普通树状数组遍历顺序相反，即 x \leftarrow x + \text{lowbit}(x) 与 x \leftarrow x - \text{lowbit}(x) 交换了。

现在给定两种操作，分别是随机对区间内一个数加 1 与求区间和等于正确答案的概率，对 998244353 取模。

树状数组点数和操作数均小于 10^{5}。

分析

显然我们需要先分析该错误树状数组的性质，然后计算其正确的概率，最后用数据结构等技巧统计答案。

分析树状数组

首先，我们知道树状数组的一个节点 \text{tree}_{x} 维护的信息为区间 \left( x - \text{lowbit}(x), x \right] 中所有数之和。

虽然错误树状数组把顺序搞反了，但是 x \leftarrow x + \text{lowbit}(x) 操作可以遍历所有覆盖到 x 的区间的性质是不变的。

然后我们考虑 x \leftarrow x - \text{lowbit}(x)，其会把区间 \left( 0, x \right] 拆分为若干段，保证不重不漏地覆盖每一个区间内的点。

这时我们容易想到，这个错误树状数组做的实际上是计算原数组的后缀和。我们可以证明这一点，大致思路是对每次查询操作分析它之前的每个 x 大于等于它的修改操作，发现其必定覆盖了这个查询操作，且查询的时候遍历到的 \text{tree} 必然与修改时遍历到的 \text{tree} 有且仅有一个公共点。借助普通树状数组的性质可以感性理解这个结论。

因为原操作是与异或和等价的，所以我们这里用异或和代替。另外规定 a_{i} 为正确操作得到的数组，\text{pre}_{x} 为区间 \left[ 1, x \right] 的异或和，\text{suf}_{x} 为区间 \left[ x, n \right] 的异或和。

那么我们分析查询操作，正确的操作得到的应该是 \text{Query}(l, r) = \text{pre}_{r} \oplus \text{pre}_{l - 1}，但实际上因为其计算的实际上是后缀和，所以得到的是 \text{suf}_{r} \oplus \text{suf}_{l - 1}，那么两个答案取异或，得到 a_{l - 1} \oplus a_{r}，其为 0 时就是结果正确的情况。

但要注意，当 l = 1 时，我们发现出题人特判了。这时有 \text{Query}(1, r) = \text{pre}_{r}，同样因为错误，所以实际上是 \text{suf}_{r}，那么两者异或得到 a_{r} \oplus \text{pre}_{n}，因为 \text{pre}_{n} 是已知的，所以只要计算 a_{r} 为 0 的概率即可。

计算概率

这一部分是本方法比较快的关键，与其他题解有较大不同。

下面为了行文方便，直接使用减一后的 l，另外对于 l = 1 的情况容易发现是可以简单拓展（甚至不用改代码）得到的。

我们考虑一对 (l, r)，发现 a_{l} = a_{r} 当且仅当 a_{l} 和 a_{r} 被改变，或者说被修改操作选中的次数之和为偶数。

所以我们考虑所有修改操作的区间，可以根据是否与 l 和 r 有交分为四类。记该修改区间的大小为 \text{len}，那么其中与 l, r 都不相交的对答案没有贡献，只与一个相交的有 \frac{1}{\text{len}} 的概率贡献一次修改，与两个都相交的有 \frac{2}{\text{len}} 的概率贡献一次修改。

我们只关心修改次数为偶数的概率，容易想到用生成函数进行描述。所以我们记修改操作 i 贡献一次修改的概率为 p_{i}，我们有 a_{l} = a_{r} 的概率为：

P = \sum _ {2 \mid k} [x^{k}] \prod _ {i} (1 - p_{i}) + p_{i} x

如果记 f(x) 为上述多项式，即

f(x) = \prod _ {i} (1 - p_{i}) + p_{i} x

显然有：

P = \frac{f(1) + f(-1)}{2}

又 f(1) = 1，所以我们只需要计算 (1 - 2 p_{i}) 的积即可。

接下来只剩普通的统计答案了，熟练树套树或 CDQ 分治的大佬可以直接开始码了。

统计答案

我们分析查询 (l, r) 的从修改 (L, R) 得到的贡献，如果 (L \le l \land l \le R < r) \lor (l < L \le r \land r \le R)，那么积会乘上 (1 - \frac{2}{R - L + 1})，如果 L \le l \le r \le R，那么积会乘上 (1 - \frac{4}{R - L + 1})。

这是一个显然的二维数点问题，可以用树套树解决，但因为没有强制在线，所以 CDQ 分治是一个明智的选择，另外我们选用树状数组维护前缀积（树状数组题当然要用树状数组做啦）。

我们发现只需要把每个查询拆分为 (l, r), (l, l), (r, r) 三部分，其中 (l, r) 除了计算两个点都覆盖到的贡献还要除去只覆盖到一个点的多计算的贡献。我们把左半边的修改和右半部的查询按照 r 从大到小排序，再按照 l 从小到大排序就可以做 CDQ 分治了。

最后有两个要注意的点，首先输出的时候判断 l = 1 的情况整个数组的异或值是否为 1，是的话概率需要取对立；其次，贡献可能为 0，因为 0 没有逆元，所以直接算会导致后面全都是 0。我们需要把 0 单独计算（实际上是长度为 2 和 4 的区间），最后判断是否是 0。

参考代码

#include <bits/stdc++.h>
#define anon_soyo 99

const int N = 1e5 + 5;
const int P = 998244353;
int n, m, op[N], ql[N], qr[N], anon[N], soyo[N];
int inv[N];

int A(int aa, int bb) {
    return aa + bb >= P ? aa + bb - P : aa + bb;
}

int S(int aa, int bb) {
    return aa - bb < 0 ? aa + P - bb : aa - bb;
}

int M(int aa, int bb) {
    return 1ll * aa * bb % P;
}

void Md(int &aa, int bb) {
    aa = 1ll * aa * bb % P;
    return;
}

int Pow(int base, int power) {
    int res = 1;
    while (power) {
        if (power & 1) {
            Md(res, base);
        }
        Md(base, base);
        power >>= 1;
    }
    return res;
}

int clo;
struct BIT {
    int t0[N], t1[N], fg[N];

    void updata0(int x) {
        while (x <= n) {
            if (fg[x] < clo) {
                fg[x] = clo;
                t0[x] = 0;
                t1[x] = 1;
            }
            ++ t0[x];
            x += x & -x;
        }
        return;
    }

    void updata1(int x, int mu) {
        while (x <= n) {
            if (fg[x] < clo) {
                fg[x] = clo;
                t0[x] = 0;
                t1[x] = 1;
            }
            Md(t1[x], mu);
            x += x & -x;
        }
        return;
    }

    int query0(int x) {
        int res = 0;
        while (x) {
            if (fg[x] < clo) {
                fg[x] = clo;
                t0[x] = 0;
                t1[x] = 1;
            }
            res += t0[x];
            x -= x & -x;
        }
        return res;
    }

    int query1(int x) {
        int res = 1;
        while (x) {
            if (fg[x] < clo) {
                fg[x] = clo;
                t0[x] = 0;
                t1[x] = 1;
            }
            Md(res, t1[x]);
            x -= x & -x;
        }
        return res;
    }
} tr1, tr2;

struct node {
    int x, y, op, id;
    bool operator < (const node &aa) const {
        if (y != aa.y) {
            return y > aa.y;
        }
        if (x != aa.x) {
            return x < aa.x;
        }
        return op < aa.op;
    }
} s[N * 3];

void cdq(int l, int r) {
    if (l == r) {
        return;
    }
    int mid = l + (r - l) / 2, cnt = 0;
    ++ clo;

    for (int i = l; i <= mid; ++ i) {
        if (op[i] != 1) {
            continue;
        }
        s[++ cnt] = (node){ql[i], qr[i], 0, i};
    }
    for (int i = mid + 1; i <= r; ++ i) {
        if (op[i] != 2) {
            continue;
        }
        if (ql[i] == 1) {
            s[++ cnt] = (node){qr[i], qr[i], 1, i};
            continue;
        }
        s[++ cnt] = (node){ql[i] - 1, qr[i], 1, i};
        s[++ cnt] = (node){qr[i], qr[i], 1, i};
        s[++ cnt] = (node){ql[i] - 1, ql[i] - 1, 1, i};
    }
    std::sort(s + 1, s + cnt + 1);

    for (int i = 1; i <= cnt; ++ i) {
        if (s[i].op == 0) {
            if (s[i].y - s[i].x + 1 == 2) {
                tr1.updata0(s[i].x);
            } else {
                tr1.updata1(s[i].x, S(1, M(2, inv[s[i].y - s[i].x + 1])));
            }
            if (s[i].x != s[i].y) {
                if (s[i].y - s[i].x + 1 == 4) {
                    tr2.updata0(s[i].x);
                } else {
                    tr2.updata1(s[i].x, S(1, M(4, inv[s[i].y - s[i].x + 1])));
                }
            }
        } else if (s[i].x == s[i].y) {
            Md(anon[s[i].id], tr1.query1(s[i].x));
            soyo[s[i].id] += tr1.query0(s[i].x);
        } else {
            Md(anon[s[i].id], tr2.query1(s[i].x));
            soyo[s[i].id] += tr2.query0(s[i].x);
            Md(anon[s[i].id], Pow(tr1.query1(s[i].x), (P - 2) * 2));
            soyo[s[i].id] -= tr1.query0(s[i].x) * 2;
        }
    }

    cdq(l, mid);
    cdq(mid + 1, r);
    return;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif

    scanf("%d%d", &n, &m);
    inv[1] = 1;
    for (int i = 2; i <= n; ++ i) {
        inv[i] = A(P - M(inv[P % i], P / i), 0);
    }
    for (int i = 1; i <= m; ++ i) {
        scanf("%d%d%d", &op[i], &ql[i], &qr[i]);
        anon[i] = 1;
    }

    cdq(1, m);
    int xo = 0;
    for (int i = 1; i <= m; ++ i) {
        if (op[i] == 2) {
            if (soyo[i] != 0) {
                anon[i] = 0;
            }
            if (ql[i] == 1 && xo == 1) {
                printf("%d\n", S(1, M(A(1, anon[i]), (P + 1) / 2)));
            } else {
                printf("%d\n", M(A(1, anon[i]), (P + 1) / 2));
            }
        } else {
            xo ^= 1;
        }
    }
    return 0;
}