P11071「QMSOIR1」DistortedFateSolution

Description

给定序列 a = ( a 1 , a 2 , ⋯   , a n ) a=(a_1,a_2,\cdots,a_n) a=(a1​,a2​,⋯,an​)，有 m m m 个操作分两种：

modify ⁡ ( l , r , x ) \operatorname{modify}(l,r,x) modify(l,r,x)：对每个 i ∈ [ l , r ] i \in [l,r] i∈[l,r] 执行 a i ← a i xor ⁡ x a_i \gets a_i \operatorname{xor} x ai​←ai​xorx. query ⁡ ( l , r ) \operatorname{query}(l,r) query(l,r)：求 ∑ i = l r ( a l or ⁡ a l + 1 or ⁡ ⋯ or ⁡ a i )   m o d   2 30 \sum\limits_{i=l}^r (a_l \operatorname{or} a_{l+1} \operatorname{or} \cdots \operatorname{or} a_i) \bmod 2^{30} i=l∑r​(al​oral+1​or⋯orai​)mod230 Limitations

1 ≤ n , m ≤ 2 × 1 0 5 1 \le n,m \le 2 \times 10^5 1≤n,m≤2×105 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n 0 ≤ a i , x ≤ 2 30 0 \le a_i,x \le 2^{30} 0≤ai​,x≤230 3 s , 100 MB 3\text{s},\textcolor{red}{100\text{MB}} 3s,100MB

Solution

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

Code

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

// Problem: P11071 「QMSOI R1」 Distorted Fate // Contest: Luogu // URL: .luogu /problem/P11071 // Memory Limit: 100 MB // Time Limit: 1000 ms // // Powered by CP Editor ( 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; }