**Problem Statement:**↵
↵
You are given an array `arr` of size\(N\)$N$. Initially, all \($arr[i]\)$ are set to 0. Now consider \(Q\)$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 \leq i \leq r\)$.↵
2. **\[2, l, r, x\]:** In this case, for each\($arr[i]\), \($, $l \leq i \leq r\)$, update the value to \($arr[i] = arr[i] \, \oplus \, x\)x$ (where \($\oplus\)$ is the XOR operation).↵
↵
### Constraints:↵
1.\($ 1 \leq N \leq 10^5\) $↵
2.\($ 1 \leq Q \leq 10^5\) $↵
3.\($ 1 \leq l \leq r \leq N\) $↵
4.\($ 1 \leq x \leq 2^{30} — 1\)- 1 $↵
↵
---↵
↵
**Approach:**↵
↵
This problem can be solved easily with a Segment Tree with Lazy Propagation, had there been no XOR updates. Lazy Propagation requires that for an update on range\($[l, r]\)$, we should be able to calculate the value of \($[l, r]\)$ after the update in \($O(1)\)$ time (or at least sub-linear time like \($O(\log n)\)$).↵
↵
For other updates, say multiply by\(x\)$x$, this would be simple. The value of \($[l, r]\)$ after the update would be:↵
↵
\[↵
\text{new\_sum} = x \times \text{* prev\_sum}↵
\]↵
↵
For XOR updates, though, this is not so straightforward.↵
↵
---↵
↵
**Simplifying the XOR Update:**↵
↵
Consider a simpler problem. Let's say that all values in `arr` can be either 0 or 1, and even\(x\)$x$ can be only 0 or 1.↵
↵
Now the sum of range\($[l, r]\)$ is \(S\)$S$, which indicates that there are \(S\)$S$ 1s and \($r — l + 1 — S\)$ 0s in \($[l, r]\)$.↵
↵
1. An update with\($x = 0\)$ won’t change anything.↵
2. An update with\($x = 1\)$ would flip 0s and 1s, so there will be \(r — l + 1 — S\)$r - l + 1 - S $ 1s and \(S\)$S$ 0s. The new sum is:↵
↵
\[↵
$r— l + 1 — S↵
\]- l + 1 - S $↵
↵
Thus, we can build a segment tree with lazy propagation for this array.↵
↵
---↵
↵
**Generalizing for the Full Problem:**↵
↵
The key idea is to notice that each number can be at most 30 bits, and we can just maintain such arrays for each of the 30 bits.↵
↵
So, we build\( \log_{max}$LOGMAX (=30) \)$ such arrays, and for each query:↵
↵
1. For sum\($[l, r]\)$, calculate \( \text${sum}_0, \text{sum}_1, \ldots, \text{sum}_{29} \)$ for each of the trees. The final sum is:↵
↵
\[↵
$\text{sum}_0 \times 2^0 + \text{sum}_1 \times 2^1 + \ldots + \text{sum}_{29} \times 2^{29}↵
\]$↵
↵
2. For the update\($[l, r]\)$ with XOR \(x\)$x$, flip \($[l, r]\)$ for the \($k^{th}\)$ tree if the \($k^{th}\)$ bit of \(x\)$x$ is set.↵
↵
--- ↵
↵
↵
~~~~~↵
↵
#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;↵
}↵
↵
~~~~~↵
↵
You are given an array `arr` of size
↵
1. **\[1, l, r\]:** In this case, calculate the sum of values of
2. **\[2, l, r, x\]:** In this case, for each
↵
### Constraints:↵
1.
2.
3.
4.
↵
---↵
↵
**Approach:**↵
↵
This problem can be solved easily with a Segment Tree with Lazy Propagation, had there been no XOR updates. Lazy Propagation requires that for an update on range
↵
For other updates, say multiply by
↵
\text{
\]
↵
For XOR updates, though, this is not so straightforward.↵
↵
---↵
↵
**Simplifying the XOR Update:**↵
↵
Consider a simpler problem. Let's say that all values in `arr` can be either 0 or 1, and even
↵
Now the sum of range
↵
1. An update with
2. An update with
↵
$r
\]
↵
Thus, we can build a segment tree with lazy propagation for this array.↵
↵
---↵
↵
**Generalizing for the Full Problem:**↵
↵
The key idea is to notice that each number can be at most 30 bits, and we can just maintain such arrays for each of the 30 bits.↵
↵
So, we build
↵
1. For sum
↵
$\text{sum}_0 \times 2^0 + \text{sum}_1 \times 2^1 + \ldots + \text{sum}_{29} \times 2^{29}
\]
↵
2. For the update
↵
--- ↵
↵
↵
~~~~~↵
↵
#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;↵
}↵
↵
~~~~~↵
