### Problem Statement:↵
↵
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 \le i \le r$.↵
2. **\[2, l, r, x\]:** In this case, for each $arr[i]$, $l \le i \le r$, update the value to $arr[i] = arr[i] \oplus x$ (where $\oplus$ is the XOR operation).↵
↵
### Constraints:↵
1. $ 1 \le N \le 10^5 $↵
2. $ 1 \le Q \le 10^5 $↵
3. $ 1 \le l \le r \le N $↵
4. $ 1 \le x \le 2^{30} - 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$, this would be simple. The value of $[l, r]$ after the update would be:↵
↵
new_sum = x * prev_sum↵
↵
For XOR updates, though, this is not so straightforward.↵
↵
---↵
↵
<spoiler summary="Simplifying the XOR Update">↵
### 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$ can be only 0 or 1.↵
↵
Now the sum of range $[l, r]$ is $S$, which indicates that there are $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 $ 1s and $S$ 0s. The new sum is:↵
↵
↵
$r - l + 1 - S $↵
↵
Thus, we can build a segment tree with lazy propagation for this array.↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Generalizing for the Full Problem:">↵
### 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 $LOGMAX (=30)$ such arrays, and for each query:↵
↵
1. For sum $[l, r]$, calculate ${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$, flip $[l, r]$ for the $k^{th}$ tree if the $k^{th}$ bit of $x$ is set.↵
</spoiler>↵
↵
--- ↵
↵
<spoiler summary="Code">↵
~~~~~cpp↵
↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
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 \le i \le r$.↵
2. **\[2, l, r, x\]:** In this case, for each $arr[i]$, $l \le i \le r$, update the value to $arr[i] = arr[i] \oplus x$ (where $\oplus$ is the XOR operation).↵
↵
### Constraints:↵
1. $ 1 \le N \le 10^5 $↵
2. $ 1 \le Q \le 10^5 $↵
3. $ 1 \le l \le r \le N $↵
4. $ 1 \le x \le 2^{30} - 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$, this would be simple. The value of $[l, r]$ after the update would be:↵
↵
new_sum = x * prev_sum↵
↵
For XOR updates, though, this is not so straightforward.↵
↵
---↵
↵
<spoiler summary="Simplifying the XOR Update">↵
### 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$ can be only 0 or 1.↵
↵
Now the sum of range $[l, r]$ is $S$, which indicates that there are $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 $ 1s and $S$ 0s. The new sum is:↵
↵
↵
$r - l + 1 - S $↵
↵
Thus, we can build a segment tree with lazy propagation for this array.↵
</spoiler>↵
↵
---↵
↵
<spoiler summary="Generalizing for the Full Problem:">↵
### 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 $LOGMAX (=30)$ such arrays, and for each query:↵
↵
1. For sum $[l, r]$, calculate ${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$, flip $[l, r]$ for the $k^{th}$ tree if the $k^{th}$ bit of $x$ is set.↵
</spoiler>↵
↵
--- ↵
↵
<spoiler summary="Code">↵
~~~~~cpp↵
↵
#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;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
