P9631 [ICPC 2020 Nanjing R] Just Another Game of Stones Solution

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分两种：

• $\mathrm{chmax}(l,r,k)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow \max (a_i,k)$.
• $\mathrm{query}(l,r,k)$：用石堆 $a_{l\cdots r}$ 和一堆 $k$ 个石子玩 Nim，求先手第一次取完石子后，后手必败的操作方案数.

Limitations

$1\le n,m\le 2\times 10^5$
$0\le a_i,k<2^{30}$
$1\le l\le r\le n$
$3\text{s},256\text{MB}$

Solution

看到 $\mathrm{chmax}$ 先来一个吉司机.
然后看查询，显然要维护 $\mathrm{xor}$ 和用来判断先手是否必胜.
考虑如何求方案数，将 $k$ 算入，设 $s$ 为这局游戏的 SG 值，若先手必胜则策略显然为 $a_i\leftarrow a_i\mathrm{xor}s$，所以把问题转化成求 $\sum [a_i>(a_i\mathrm{xor}s)]$.
考虑异或性质，发现只需要维护某位为 $1$ 的数的数量，查询时就找到 $s$ 最高位，统计这位为 $1$ 的即可.
需要的信息都可以在吉司机上维护，于是就做完了.
注意 $\infty$ 要开够.

Code

$4.25\text{KB},578\text{ms},114.35\text{MB}\text{(in total, C++ 20 with O2)}$

// Problem: P9631 [ICPC2020 Nanjing R] Just Another Game of Stones
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9631
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}

const int inf = 2147483647;
struct Node {
    int l, r;
    int min, sec, cnt, tag, sum;
    array<int, 30> bits;
};
using Tree = vector<Node>;
inline int ls(int u) { return 2 * u + 1; }
inline int rs(int u) { return 2 * u + 2; }

inline void pushup(Tree& tr, int u) {
    tr[u].sum = tr[ls(u)].sum ^ tr[rs(u)].sum;
    if (tr[ls(u)].min == tr[rs(u)].min) {
        tr[u].min = tr[ls(u)].min;
        tr[u].cnt = tr[ls(u)].cnt + tr[rs(u)].cnt;
        tr[u].sec = min(tr[ls(u)].sec, tr[rs(u)].sec);
    }
    else if (tr[ls(u)].min < tr[rs(u)].min) {
        tr[u].min = tr[ls(u)].min;
        tr[u].cnt = tr[ls(u)].cnt;
    	tr[u].sec = min(tr[ls(u)].sec, tr[rs(u)].min);
    }
    else {
        tr[u].min = tr[rs(u)].min;
        tr[u].cnt = tr[rs(u)].cnt;
        tr[u].sec = min(tr[ls(u)].min, tr[rs(u)].sec);
    }
    for (int i = 0; i < 30; i++) {
        tr[u].bits[i] = tr[ls(u)].bits[i] + tr[rs(u)].bits[i];
    }
}

inline void build(Tree& tr, int u, int l, int r, const vector<int>& A) {
    tr[u].l = l;
    tr[u].r = r;
    tr[u].tag = -1;
    if (l == r) {
        tr[u].min = tr[u].sum = A[l];
        tr[u].sec = inf;
        tr[u].cnt = 1;
        for (int i = 0; i < 30; i++) tr[u].bits[i] = (A[l] >> i & 1);
        return;
    }
    
    const int mid = (l + r) >> 1;
    build(tr, ls(u), l, mid, A);
    build(tr, rs(u), mid + 1, r, A);
    pushup(tr, u);
}

inline void apply(Tree& tr, int u, int v) {
    if (tr[u].min >= v) return;
    tr[u].sum ^= (tr[u].cnt & 1) * (tr[u].min ^ v);
    for (int i = 0; i < 30; i++)
        tr[u].bits[i] += ((v >> i & 1) - (tr[u].min >> i & 1)) * tr[u].cnt;
    tr[u].min = tr[u].tag = v;
}

inline void pushdown(Tree& tr, int u) {
    if (tr[u].tag != -1) {
        apply(tr, ls(u), tr[u].tag);
        apply(tr, rs(u), tr[u].tag);
        tr[u].tag = -1;
    }
}

inline void update(Tree& tr, int u, int l, int r, int v) {
    if (tr[u].min >= v) return;
    if (l <= tr[u].l && tr[u].r <= r && tr[u].sec > v) return apply(tr, u, v);
    const int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (l <= mid) update(tr, ls(u), l, r, v);
    if (r > mid) update(tr, rs(u), l, r, v);
    pushup(tr, u);
}

inline int qsum(Tree& tr, int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    const int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (r <= mid) return qsum(tr, ls(u), l, r);
    else if (l > mid) return qsum(tr, rs(u), l, r);
    else return qsum(tr, ls(u), l, r) ^ qsum(tr, rs(u), l, r);
}

inline int qbit(Tree& tr, int u, int l, int r, int k) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].bits[k];
    const int mid = (tr[u].l + tr[u].r) >> 1;
    pushdown(tr, u);
    if (r <= mid) return qbit(tr, ls(u), l, r, k);
    else if (l > mid) return qbit(tr, rs(u), l, r, k);
    else return qbit(tr, ls(u), l, r, k) + qbit(tr, rs(u), l, r, k);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	scanf("%d %d", &n, &m);
	
	vector<int> a(n);
	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	Tree tr(n << 2);
	build(tr, 0, 0, n - 1, a);
	
	auto get = [&](int l, int r, int x) {
	    int sg = qsum(tr, 0, l, r) ^ x, bit = -1;
	    for (int i = 0; i < 30; i++)
	        if (sg >> i & 1) bit = i;
	    if (bit == -1) return 0;
	    return qbit(tr, 0, l, r, bit) + (x >> bit & 1);
	};
	
	for (int i = 0, op, l, r, v; i < m; i++) {
	    scanf("%d %d %d %d", &op, &l, &r, &v);
	    l--, r--;
	    if (op == 1) update(tr, 0, l, r, v);
	    else printf("%d\n", get(l, r, v));
	}
	
	return 0;
}