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;
}