#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
#include <string>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
#define rep(x, a, b) for (ll x = a; x < b; x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define sz(a) a.size()
#define resz(a, n) a.resize(n)
vll oranges;
vpll segtree;
vpll interval;
pll combine(pll x, pll y) {
return mp(x.first ^ y.first, x.second ^ y.second);
}
pll segtree_assign(ll val, int pos) {
if (pos & 1) {
return mp(val, 0);
} else {
return mp(0, val);
}
}
void build(int cur, int l, int r) {
interval[cur] = mp(l, r);
if (l == r) {
segtree[cur] = segtree_assign(oranges[l], l);
return;
}
int m = (l + r) / 2;
build(2 * cur, l, m);
build(2 * cur + 1, m + 1, r);
segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}
pll query(int cur, int l, int r) {
if ((interval[cur].first > r) || (interval[cur].second < l)) {
return mp(0, 0);
}
if ((l <= interval[cur].first) && (interval[cur].second <= r)) {
return segtree[cur];
}
return combine(query(2 * cur, l, r), query(2 * cur + 1, l, r));
}
void update(int cur, int x, ll val) {
if ((interval[cur].first > x) || (x > interval[cur].second)) {
return;
}
if (interval[cur].first == interval[cur].second) {
segtree[cur] = segtree_assign(val, x);
return;
}
update(2 * cur, x, val);
update(2 * cur + 1, x, val);
segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n, q;
cin >> n >> q;
resz(oranges, n);
resz(segtree, 2 * n);
resz(interval, 2 * n);
rep(i, 0, n) {
cin >> oranges[i];
}
build(1, 0, n - 1);
/*
rep(i, 0, 2 * n) {
cout << "(" << segtree[i].first << ", " << segtree[i].second << ") ";
}
cout << endl;
*/
ll tmpa, tmpb, tmpc;
rep(i, 0, q) {
cin >> tmpa >> tmpb >> tmpc;
if (tmpa == 1) {
update(1, tmpb - 1, tmpc);
} else {
if ((tmpc + tmpb) & 1) {
cout << "0\n";
} else {
// odd length
pll res = query(1, tmpb - 1, tmpc - 1);
//cout << "(" << res.first << ", " << res.second << ")" << endl;
if (tmpb & 1) {
// take even indexed, which is res.second
cout << res.second << "\n";
} else {
cout << res.first << "\n";
}
}
}
/*
rep(i, 0, 2 * n) {
cout << "(" << segtree[i].first << ", " << segtree[i].second << ") ";
}
cout << endl;
*/
}
return 0;
}
// for a range: find xor of all elements, all pairs of consequtive, all triplets of consequtive, etc...
// so for x in [l, r] we want to find if this coordinate contributes or not...
// the number of ranges which include x is:
// (x - l + 1) * (r - x + 1)
// when (l - 1) + (r + 1) = r - l is odd, this number ^^ is always even so answer is 0
// when r - l is even, then x=l, l + 2, l + 4, ..., r - 2, r contribute to answer
// so we have 2 segment-trees, for even and odd
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
42 ms |
31140 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
