题解：P8526 [Ynoi2078] 《How to represent part-whole hierarchies in a neural network》阅读报告（更新中...）

Nangu · 2025-03-14 19:34:46 · 题解

我们考虑对 r 进行扫描线。

设当前枚举到右端点 p，a_i 表示左端点为 i 时二元组的权值，b_i 表示数组 a 的历史和，则对于询问 [l, r] 答案为 \bigoplus_{i=l}^r b_i。

我们需要做的操作：

对于 i \in [l, r]，a_i+1 \to a_i。
对于 i \in [1, p]，b_i \operatorname{xor} a_i\to b_i。
查询 b 的区间异或和。

考虑序列分块。我们先预处理出 f_{o, x} 表示第 o 块 \bigoplus_{i=bl}^{br} {(a_i+x)} 的值，其中 x\le B。

对于第一类操作：

散块：暴力修改，暴力重构。
整块：我们维护一个 tag 数组，每次修改整块时 tag[o]++，若 tag_o=B，须重构整块。

对于第二类操作：

散块：暴力重构。
整块：直接令 sumb_o \operatorname{xor} f_{o, tag_o} \to sumb_o，同时维护一个桶 k，每次将 tag_o 加入 k_o，用于维护 b。

第三类是平凡的。

现在我们只剩下了一个问题：如何暴力重构整块？

我们需要干两件事：重新计算 f 的值，以及将懒标记下放更新 b 的值。

更新 b 的值相当于对于每一个在桶内的值 x，执行 b_i \operatorname{xor} (a_i+x) \to b_i。容易发现这个过程和计算 f 的过程非常像，因此我们下文只讨论 f 的处理方法。

注意到 a+b 可以看作 a\operatorname{xor}b 再加上 a+b 所产生的每一个进位。因此，我们可以逐位计算 f_x 的进位的个数，则原问题就转化为求对于每一个 2 的正整数幂 k 以及 x，计算 x \bmod k+ a_i \bmod k \ge k 的个数。

这样直接枚举值域并双指针的做法是 O(B\log n) 的，考虑进行一点优化。

我们将 k 分成 \le B 和 >B 两类。

对于第一类 k，令 dp_{k, y} 表示 x \bmod k=y 的 x 在 k 上的贡献。这个数组的总元素个数是 O(B) 的。容易线性求出。

对于第二类 k，容易发现，此时 x\bmod k=x。发现对于任意的 a_i，a_i 对一些 x 造成贡献的一定是 k 的一段前缀，且这段前缀里 x 的值域完全相同，于是直接前缀和统计即可。

~~如果你看到这里一脸蒙逼，请结合下面的代码一起食用。~~

const int B=511;
void rebuild(const int o){
    const int l=bl[o], r=br[o];
    rep(i, l, r) num[a[i]&B]^=1;//开一个桶
    per(k, 8, 0){
        int s=1<<k+1, now=0;
        rep(i, 1, s-1){
            now^=num[s-i];
            if(now) pre[k][i]=s;//pre[k][i] 表示在 模 2^k 下，i 的贡献
        }
        rep(i, 1, s-1) if(i>>k&1) num[i^1<<k]^=num[i], num[i]=0;
    }
    num[0]=0;
    rep(k, 0, 7){
        const int s=1<<k+1;
        rep(i, 1, s-1){
            pre[k+1][i]^=pre[k][i];
            pre[k+1][i|s]^=pre[k][i];
            //进行前缀和
            pre[k][i]=0;
        }
    }
    rep(i, 0, B) f[o][i]=pre[8][i], pre[8][i]=0;//算出第一部分(x<=B)的贡献
    rep(i, l, r){
        int p=__builtin_ctz((a[i]>>9)^O);
        if(p) num[(1<<10)-(a[i]&1023)]^=(1<<10+p)-(1<<10);
        /* 
        第二部分。
        此时 x<=B<=k/2
        想要让 x+a_i%k>=k，a_i 第10，11，12一直到log2(k)位必须为1
        这就是为什么“贡献一定是一个k的前缀”
        p即为 a_i 的最长连续1段的长度
        */
    }
    int now=0;
    rep(i, 0, B) now^=num[i], num[i]=0, f[o][i]^=now;
    int s=0;
    rep(i, l, r) s^=a[i];//计算不进位的贡献
    rep(i, 0, B){
        f[o][i]^=s;
        if(r-l+1&1) f[o][i]^=i;
    }
}