P11071 「QMSOI R1」 Distorted Fate Solution

Description

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

• $\mathrm{modify}(l,r,x)$：对每个 $i\in [l,r]$ 执行 $a_i\leftarrow a_i\mathrm{xor}x$.
• $\mathrm{query}(l,r)$：求 $\sum _{i=l}^r(a_l\mathrm{or}{a}_{l+1}\mathrm{or}\cdots \mathrm{or}{a}_i)\mathrm{mod}{2}^{30}$

Limitations

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

Solution

直接做不方便，考虑拆位计算.
对每个位开一个线段树，于是 $\mathrm{modify}$ 就是区间异或 $1$.
容易发现对于某个位 $k$，前缀 $\mathrm{or}$ 中第 $k$ 位为 $1$ 的元素是一段后缀，将其左端点 $m$ 二分出来，那么这一位的贡献是 $2^k(r-m+1)$.
空间不够，线段树要共用空间，所以需要离线.

Code

$3.20\text{KB},2.05\text{s},18.01\text{MB}\text{(in total, C++20 with O2)}$

// Problem: P11071 「QMSOI R1」 Distorted Fate
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11071
// Memory Limit: 100 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using ui32 = unsigned int;
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;
}constexpr int mask = (1 << 30) - 1;
struct Node {int l, r;int size;bool rev;
};
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].size = tr[ls(u)].size + tr[rs(u)].size;
}inline void rev(Tree& tr, int u) {tr[u].rev ^= 1;tr[u].size = tr[u].r - tr[u].l + 1 - tr[u].size;
}inline void pushdown(Tree& tr, int u) {if (tr[u].rev) {rev(tr, ls(u)), rev(tr, rs(u));tr[u].rev = false;}
}inline void build(Tree& tr, int u, int l, int r, int bit, const vector<int>& a) {tr[u].l = l;tr[u].r = r;tr[u].rev = false;if (l == r) {tr[u].size = a[l] >> bit & 1;return;}int mid = (l + r) >> 1;build(tr, ls(u), l, mid, bit, a);build(tr, rs(u), mid + 1, r, bit, a);pushup(tr, u);
}inline void update(Tree& tr, int u, int l, int r) {if (l <= tr[u].l && tr[u].r <= r) return rev(tr, u);int mid = (tr[u].l + tr[u].r) >> 1;pushdown(tr, u);if (l <= mid) update(tr, ls(u), l, r);if (r > mid) update(tr, rs(u), l, r);pushup(tr, u);
}inline int query(Tree& tr, int u, int l, int r) {if (l > r) return 0;if (l <= tr[u].l && tr[u].r <= r) return tr[u].size;int mid = (tr[u].l + tr[u].r) >> 1, res = 0;pushdown(tr, u);if (l <= mid) res += query(tr, ls(u), l, r);if (r > mid) res += query(tr, rs(u), l, r);return res;
}inline int find(Tree& tr, int u, int k) {if (tr[u].l == tr[u].r) return tr[u].l;pushdown(tr, u);if (tr[ls(u)].size > k) return find(tr, ls(u), k);return find(tr, rs(u), k - tr[ls(u)].size);
}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]);vector<array<int, 4>> queries(m);for (auto& [op, l, r, x] : queries) {scanf("%d %d %d", &op, &l, &r);l--, r--;if (op == 1) scanf("%d", &x);} vector<ui64> ans(m);Tree tr(n << 2);for (int lg = 0; lg < 30; lg++) {build(tr, 0, 0, n - 1, lg, a);for (int i = 0; i < m; i++) {auto& [op, l, r, x] = queries[i];if (op == 1) {if (x >> lg & 1) update(tr, 0, l, r);} else {int s = query(tr, 0, 0, l - 1), m = find(tr, 0, s);if (m > r || tr[0].size <= s) continue;ans[i] += 1ULL * (r - m + 1) * (1 << lg);}}}for (int i = 0; i < m; i++) if (queries[i][0] == 2) printf("%llu\n", ans[i] & mask);return 0;
}