题解：CF2271H2 Personal Issues (Hard Version)

starish · 2026-11-13 17:24:58 · 题解

书接上回

现在我们要优化区间 dp 的速度，让它通过 n \le 2 \times 10 ^ 5，显然可以使用 bitset，给出不手写 bitset 的代码片段。

for (int i = 0; i < len; i++) {
    p[i] = (n - len - pre[i]) & 1;
    q[i] = pre[i] & 1;
}
for (int i = 0; i + 2 < len; i++) {
    f1[i] = (n - len - (sz[i + 1] - 1)) & 1;
    f2[i] = (n - len - (sz[i + 1] - 1) + 1) & 1;
}
for (int l = 2; l <= len - 2; l++) {
    a = (tmp ^ ((f1 >> 1) & f1));
    b = (tmp ^ ((f2 >> 1) & f2));
    c = (p ^ (q >> l));
    f1 = a | (c & ~b);
    f2 = b | (~c & ~a);
}

但是无法通过，可以手写 bitset，并把操作压到一个 word 里，可以极限通过（1984/2000 ms），以下给出与 easy version 不同的代码片段。

int M = min(N, 2 * len);
BitSet bs(M);
bs.init();
for (int i = 0; i < len; i++) {
    if ((n - len - pre[i]) & 1) bs.setp(i);
    if (pre[i] & 1) bs.setq(i);
}
for (int i = 0; i + 2 < len; i++) {
    if ((n - len - (sz[i + 1] - 1)) & 1) bs.set1(i);
    if ((n - len - (sz[i + 1] - 1) + 1) & 1) bs.set2(i);
}
for (int l = 2; l <= len - 2; l++) bs.step(l);
int ans1 = bs.get1(), ans2 = bs.get2();
int v = ((sz[0] + sz[len - 1] - 2) & 1);
if (v == 0) cout << ans1 << '\n';
else cout << max(ans1, v - ans2) << '\n';

struct BitSet {
    using u64 = unsigned long long;
    int nbit, W;
    vector<u64> f1, f2, p, q, tmp;
    BitSet(int n = 0) : nbit(n), W((n + 63) >> 6),
    f1(W + 1), f2(W + 1), p(W + 1), q(2 * W + 2), tmp(W + 1) {}
    void init() {
        fill(tmp.begin(), tmp.end(), ~0ULL);
        if (W) {
            if (nbit & 63) tmp[W - 1] &= (1ULL << (nbit & 63)) - 1;
            tmp[W] = 0;
        }
    }
    inline void set1(int i) { f1[i >> 6] |= 1ULL << (i & 63); }
    inline void set2(int i) { f2[i >> 6] |= 1ULL << (i & 63); }
    inline void setp(int i) { p[i >> 6]  |= 1ULL << (i & 63); }
    inline void setq(int i) { q[i >> 6]  |= 1ULL << (i & 63); }
    void step(int l) {
        int wd = l >> 6, sh = l & 63;
        for (int w = 0; w < W; ++w) {
            // x1 对应 (f1 >> 1) & f1 的第 w 个 word
            //    这里 f1w = f1 当前 word，f1n = f1 下一个 word
            //    (f1w >> 1) | (f1n << 63) 就是 f1 >> 1 在 word w 上的值
            u64 f1w = f1[w], f1n = f1[w + 1];
            u64 x1  = ((f1w >> 1) | (f1n << 63)) & f1w;
            // x2 对应 (f2 >> 1) & f2 的第 w 个 word
            u64 f2w = f2[w], f2n = f2[w + 1];
            u64 x2  = ((f2w >> 1) | (f2n << 63)) & f2w;
            // qs 对应 (q >> l) 的第 w 个 word
            int qi = w + wd;
            u64 qs = q[qi] >> sh;
            if (sh) qs |= q[qi + 1] << (64 - sh);
            // cw 对应 c = p ^ (q >> l) 的第 w 个 word
            u64 cw = p[w] ^ qs;
            // aw 对应 a = tmp ^ x1 的第 w 个 word
            //    (tmp 在有效位上是全 1，故 aw 即 ~x1)
            u64 aw = tmp[w] ^ x1;
            // bw 对应 b = tmp ^ x2 的第 w 个 word
            u64 bw = tmp[w] ^ x2;
            // 写回 f1、f2，对应:
            //   f1 = a | (c & ~b);
            //   f2 = b | (~c & ~a);
            f1[w] = aw | (cw & ~bw);
            f2[w] = bw | (~cw & ~aw);
        }
    }
    int get1() const { return f1[0] & 1; }
    int get2() const { return f2[0] & 1; }
};