P9631 [ICPC2020 Nanjing R] Just Another Game of Stones 题解

· · 题解

吉司机线段树。

操作为区间修改取 \max，这是吉司机线段树模板，容易维护。

考虑询问如何实现。考虑 Nim 游戏的结论：令 s=x\oplus a_l\oplus a_{l+1}\oplus\dots\oplus a_r，先手必败当且仅当 s=0。可以用线段树维护区间异或和，这样可以判断先手是否必胜。

考虑如何得出可操作方案数。不妨把 x 算入 a，则如果此时先手有必胜策略，策略显然是 a_i\gets a_i\oplus s。而 Nim 游戏要求是减少数量，因此转化为询问满足 a_i>a_i\oplus s 的数量。

考虑异或的性质。对于 s 二进制下的最高为 1 的位，显然存在 a_i 当前位为 1。对于该位为 1 的 a_i，异或上 s 之后显然会变小；反之则一定变大。因此只需要统计某一位为 1 的数的个数即可。这些信息用吉司机线段树均容易维护。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, q, a[N];
struct node {
    int mn, se, mncnt, tag;
    int xors, cnt[30];
} t[N << 2];
void push_up(int p) {
    t[p].xors = t[p << 1].xors ^ t[p << 1 | 1].xors;
    for (int i = 0; i < 30; i++) t[p].cnt[i] = t[p << 1].cnt[i] + t[p << 1 | 1].cnt[i];
    if (t[p << 1].mn == t[p << 1 | 1].mn) {
        t[p].mn = t[p << 1].mn, t[p].mncnt = t[p << 1].mncnt + t[p << 1 | 1].mncnt;
        t[p].se = min(t[p << 1].se, t[p << 1 | 1].se);
    } else if (t[p << 1].mn < t[p << 1 | 1].mn) {
        t[p].mn = t[p << 1].mn, t[p].mncnt = t[p << 1].mncnt;
        t[p].se = min(t[p << 1].se, t[p << 1 | 1].mn);
    } else if (t[p << 1].mn > t[p << 1 | 1].mn) {
        t[p].mn = t[p << 1 | 1].mn, t[p].mncnt = t[p << 1 | 1].mncnt;
        t[p].se = min(t[p << 1].mn, t[p << 1 | 1].se);
    }
}
void build(int p, int l, int r) {
    t[p].tag = -1;
    if (l == r) {
        t[p].mn = t[p].xors = a[l], t[p].se = INT_MAX, t[p].mncnt = 1;
        for (int i = 0; i < 30; i++) t[p].cnt[i] = (a[l] >> i & 1);
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    push_up(p);
}
void set_tag(int p, int v) {
    if (t[p].mn >= v) return;
    t[p].xors ^= ((t[p].mncnt & 1) * (t[p].mn ^ v));
    for (int i = 0; i < 30; i++)
        t[p].cnt[i] += ((v >> i & 1) - (t[p].mn >> i & 1)) * t[p].mncnt;
    t[p].mn = t[p].tag = v;
}
void push_down(int p) {
    if (t[p].tag == -1) return;
    set_tag(p << 1, t[p].tag), set_tag(p << 1 | 1, t[p].tag);
    t[p].tag = -1;
}
void update(int p, int l, int r, int x, int y, int v) {
    if (t[p].mn >= v) return;
    if (x <= l && r <= y && v < t[p].se) {
        set_tag(p, v);
        return;
    }
    push_down(p);
    int mid = (l + r) >> 1;
    if (x <= mid) update(p << 1, l, mid, x, y, v);
    if (mid < y) update(p << 1 | 1, mid + 1, r, x, y, v);
    push_up(p);
}
int query1(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) return t[p].xors;
    push_down(p);
    int mid = (l + r) >> 1, res = 0;
    if (x <= mid) res ^= query1(p << 1, l, mid, x, y);
    if (mid < y) res ^= query1(p << 1 | 1, mid + 1, r, x, y);
    return res;
}
int query2(int p, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return t[p].cnt[k];
    push_down(p);
    int mid = (l + r) >> 1, res = 0;
    if (x <= mid) res += query2(p << 1, l, mid, x, y, k);
    if (mid < y) res += query2(p << 1 | 1, mid + 1, r, x, y, k);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    for (int i = 1, op, l, r, x; i <= q; i++) {
        cin >> op >> l >> r >> x;
        if (op == 1) {
            update(1, 1, n, l, r, x);
        } else {
            int y = query1(1, 1, n, l, r) ^ x, b = -1;
            for (int j = 0; j < 30; j++)
                if (y >> j & 1) b = j;
            if (b == -1) {
                cout << "0\n";
                continue;
            }
            int ans = query2(1, 1, n, l, r, b) + (x >> b & 1);
            cout << ans << '\n';
        }
    }
    return 0;
}