#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef pair <int, int> pii;
const int MAX = 1 << 17;
int n, q, arr[MAX];
pair <int, pii> nodes[2 * MAX];
struct tournament
{
pair <int, pii> merge_nodes(pair <int, pii> node1, int l1, int r1, pair <int, pii> node2, int l2, int r2){
pair <int, pii> res;
res.f = node1.f ^ node2.f;
if(r2 - l2 == 1) res.f ^= node1.s.f;
if(r1 - l1 == 1) res.f ^= node2.s.s;
if(r1 - l1 == 1 && r2 - l2 == 1){
res.s.f = node1.s.f;
res.s.s = node2.s.s;
}
else if(r1 - l1 == 1){
res.s.f = node1.s.f ^ node2.s.s;
res.s.s = node2.s.f;
}
else if(r2 - l2 == 1){
res.s.f = node1.s.f ^ node2.s.f;
res.s.s = node1.s.s;
}
else{
res.s.f = node1.s.f ^ node2.s.f;
res.s.s = node1.s.s ^ node2.s.s;
}
return res;
}
void build(int* arr, int arr_size, int node = 1, int l = 0, int r = 2 * MAX){
//cout << node << ' ' << l << ' ' << r << ' ' << n << ' ' << q << '\n';
if(r - l == 1){
nodes[node] = {arr[l], {arr[l], arr[l]}};
return;
}
int m = (l + r) / 2;
build(arr, arr_size, 2 * node, l, m);
if(m < arr_size) build(arr, arr_size, 2 * node + 1, m, r);
nodes[node] = merge_nodes(nodes[2 * node], l, m, nodes[2 * node + 1], m, r);
}
void change(int ind, int val, int node = 1, int l = 0, int r = 2 * MAX){
if(r - l == 1){
nodes[node] = {val, {val, val}};
return;
}
int m = (l + r) / 2;
if(ind < m) change(ind, val, 2 * node, l, m);
else change(ind, val, 2 * node + 1, m, r);
nodes[node] = merge_nodes(nodes[2 * node], l, m, nodes[2 * node + 1], m, r);
}
pair <pair <int, pii>, pii> query(int lq, int rq, int node = 1, int l = 0, int r = 2 * MAX){
//cout << lq << ' ' << rq << ' ' << node << ' ' << l << ' ' << r << '\n';
if(l >= lq && r <= rq) return {nodes[node], {l, r}};
int m = (l + r) / 2;
pair <pair <int, pii>, pii> res;
if(!(l >= rq || m <= lq) && !(m >= rq || r <= lq)){
pair <pair <int, pii>, pii> node1 = query(lq, rq, 2 * node, l, m);
pair <pair <int, pii>, pii> node2 = query(lq, rq, 2 * node + 1, m, r);
res.f = merge_nodes(node1.f, node1.s.f, node1.s.s, node2.f, node2.s.f, node2.s.s);
res.s.f = node1.s.f;
res.s.s = node2.s.s;
}
else if(!(l >= rq || m <= lq)) res = query(lq, rq, 2 * node, l, m);
else res = query(lq, rq, 2 * node + 1, m, r);
return res;
}
};
tournament tour;
int main()
{
cin >> n >> q;
for(int i = 0; i < n; i++) cin >> arr[i];
//cout << n << ' ' << q << '\n';
//for(int i = 0; i < n; i++) cout << arr[i] << ' ';
tour.build(arr, n);
//cout << n << ' ' << q << '\n';
//for(int i = 0; i < n; i++) cout << arr[i] << ' ';
//cout << q << '\n';
while(q--){
int mode;
cin >> mode;
if(mode == 1){
int ind, val;
cin >> ind >> val;
tour.change(ind - 1, val);
}
else{
int l, r;
cin >> l >> r;
cout << tour.query(l - 1, r).f.f << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
59 ms |
1348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
