Submission #1219840

#TimeUsernameProblemLanguageResultExecution timeMemory
1219840khomeRack (eJOI19_rack)C++20
0 / 100
0 ms320 KiB
#include<bits/stdc++.h> using namespace std; #define int long long // const int INF = 1e18; const int NEU = 0; struct node { int el0, el1; }; node make_node(int i1 = NEU, int i2 = NEU){ node a; a.el0 = i1; a.el1 = i2; return a; } node merge(node i1, node i2){ return (make_node(i1.el0^i2.el0, i1.el1^i2.el1)); } struct SegTree { int n, N = 1; vector<node> tree; SegTree(vector<int> &a){ n = a.size(); while (N < n) N *= 2; tree.assign(2*N, make_node()); for (int i = 0; i < n; i++) { if (i%2 == 0) tree[i+N] = make_node(a[i], 0); if (i%2 == 1) tree[i+N] = make_node(0, a[i]); // cout << tree[i+N] } for (int i = N-1; i >= 1; i--) { tree[i] = merge(tree[i << 1], tree[(i << 1) + 1]); } } void update(int i, int x){ node g; if (i%2 == 0) g = make_node(x, 0); if (i%2 == 1) g = make_node(0, x); i+=N; tree[i] = g; i >>= 1; while (i > 1){ tree[i] = merge(tree[i << 1], tree[(i << 1) + 1]); i >>= 1; } } node get(int l, int r){ node ans = make_node(); int so = l % 2; l+=N; r+=N; while (l < r) { if (l & 1){ ans = merge(ans, tree[l]); l++; } if (r & 1){ r--; ans = merge(ans, tree[r]); } l >>= 1; r >>= 1; } return ans; } }; void solve(){ int n, q; cin >> n >> q; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } SegTree sg(v); for (int i = 0; i < q; i++) { int p, l, r; cin >> p >> l >> r; if (p == 1){ sg.update(l-1, r); } else { if ((r - l + 1) % 2 == 0) {cout << 0 << endl; continue;} if (l == r) {cout << v[l-1] << endl; continue;} l--; if (l % 2 == 0) cout << sg.get(l, r).el0; if (l % 2 == 1) cout << sg.get(l, r).el1; cout << endl; } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while(t--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...