Lazy Propogation with Xor range updates and range sum queries

Revision en2, by one_autum_leaf, 2024-10-05 12:33:03

Consider the following problem: You are given an array arr of size N. Initially all arr[i] are set to 0. Now consider Q queries, where each query is of one of the following two types: 1. [1, l, r]: In this case calculate the sum of values of arr[i] for l <= i <= r. 2. [2, l, r, x]: In this case for each arr[i], l <= i <= r, update the value to arr[i] = arr[i] ^ x (where ^ is the XOR operation).

Constraints: 1 <= N <= 10 ** 5 1 <= Q <= 10 ** 5 1 <= l <= r <= N 1 <= x <= 2 ** 30 — 1

Approach:


#include <bits/stdc++.h> using namespace std; //#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx,avx2,avx512,fma") template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; } void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #ifdef LOCAL #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif #define ll long long #define ld long double #define PI 3.1415926535897932384626433832795l // -------------------------<rng>------------------------- // RANDOM NUMBER GENERATOR mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); #define SHUF(v) shuffle(all(v), RNG); // Use mt19937_64 for 64 bit random numbers. struct LazySegmentTree { int n; vector<ll> L, R; vector<int> val; vector<bool> lazy; LazySegmentTree(int sz) { n = 4 * sz; L.resize(n); R.resize(n); lazy.resize(n); val.resize(n); n >>= 1; init(1, 0, sz - 1); } void init(int node, int l, int r) { if (l > r) { return; } L[node] = l; R[node] = r; if (l < r) { int mid = (l + r) / 2; init(2 * node, l, mid); init(2 * node + 1, mid + 1, r); } } void flip(int node){ lazy[node] = lazy[node] ^ 1; val[node] = (R[node] - L[node] + 1) - val[node]; // Updating sum for range } void propagate(int node) { if(L[node] < R[node]){ if(lazy[node]){ flip(2 * node); flip(2 * node + 1); lazy[node] = 0; } } } void set(int node, int l, int r) { if (r < L[node] || R[node] < l) { return; } if (l <= L[node] && R[node] <= r) { flip(node); } else { propagate(node); set(2 * node, l, r); set(2 * node + 1, l, r); val[node] = val[2 * node] + val[2 * node + 1]; } } ll get(int node, int l, int r) { if (r < L[node] || R[node] < l) { return 0; // Out of range } if (l <= L[node] && R[node] <= r) { return val[node]; } propagate(node); ll left_sum = get(2 * node, l, r); ll right_sum = get(2 * node + 1, l, r); return left_sum + right_sum; } }; const int LOGMAX = 30; vector<ll> solve(int n, vector<vector<int>> &queries) { vector<LazySegmentTree> tree; for(int k = 0; k < LOGMAX; ++k){ tree.push_back(LazySegmentTree(n + 1)); } vector<ll> res; for(vector<int> &query: queries){ int type = query[0]; if(type == 1){ int l = query[1]; int r = query[2]; ll sum = 0; for(int k = 0; k < LOGMAX; ++k){ sum += (1ll << k) * tree[k].get(1, l, r); } res.push_back(sum); } else{ int l = query[1]; int r = query[2]; int x = query[3]; for(int k = 0; k < LOGMAX; ++k){ if(1 & (x >> k)){ tree[k].set(1, l, r); } } } } return res; } vector<ll> brute(int n, vector<vector<int>> &queries) { vector<int> arr(n + 1); vector<ll> res; for(vector<int> &query: queries){ int type = query[0]; if(type == 1){ int l = query[1]; int r = query[2]; ll sum = 0; for(int i = l; i <= r; ++i){ sum += arr[i]; } res.push_back(sum); } else{ int l = query[1]; int r = query[2]; int x = query[3]; for(int i = l; i <= r; ++i){ arr[i] = arr[i] ^ x; } } } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vector<vector<int>> queries(q); for(int i = 0; i < q; ++i){ int type, l, r; cin >> type >> l >> r; queries[i] = {type, l, r}; if(type == 2){ int x; cin >> x; queries[i].push_back(x); } } for(ll elem: brute(n, queries)){ cout << elem << '\n'; } assert(solve(n, queries) == brute(n, queries)); return 0; }

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English one_autum_leaf 2024-10-06 09:42:25 0 (published)
en9 English one_autum_leaf 2024-10-06 09:41:52 8073 Tiny change: ' - 1 $\n\n[problem:2' -> ' - 1 $\n\nProblem Link - [problem:2' (saved to drafts)
en8 English one_autum_leaf 2024-10-05 13:20:13 6 (published)
en7 English one_autum_leaf 2024-10-05 13:19:14 195 Tiny change: 'e">\n~~~~~\n\n#inclu' -> 'e">\n~~~~~cpp\n\n#inclu' (saved to drafts)
en6 English one_autum_leaf 2024-10-05 13:15:14 371 Tiny change: ' <= x <= 2^{30} &mdash; 1\)\n\n--' -> ' <= x <= 2_30 - 1\)\n\n--' (published)
en5 English one_autum_leaf 2024-10-05 12:57:05 2408
en4 English one_autum_leaf 2024-10-05 12:52:00 2158
en3 English one_autum_leaf 2024-10-05 12:51:31 1405 Tiny change: '```\nConsider' -> '```text\nConsider'
en2 English one_autum_leaf 2024-10-05 12:33:03 541
en1 English one_autum_leaf 2024-10-05 12:28:59 4585 Initial revision (saved to drafts)