Task: | Xor sum |
Sender: | Nallue |
Submission time: | 2024-09-23 16:30:35 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.56 s | details |
Code
#include <iostream>#include <vector>#include <climits>using namespace std;class SegmentTreeSum {vector<int> tree;int n;public:SegmentTreeSum(const vector<int>& array) {n = array.size();tree.resize(2 * n);build(array);}void build(const vector<int>& array) {for (int i = 0; i < n; i++)tree[n + i] = array[i];for (int i = n - 1; i > 0; --i)tree[i] = tree[2 * i] ^ tree[2 * i + 1];}int rangeSum(int l, int r) {int sum = 0;l += n; r += n;while (l < r) {if (l & 1) sum ^= tree[l++];if (r & 1) sum ^= tree[--r];l >>= 1; r >>= 1;}return sum;}void update(int idx, int value) {idx += n;tree[idx] = value;for (idx >>= 1; idx > 0; idx >>= 1) {tree[idx] = tree[2 * idx] ^ tree[2 * idx + 1];}}};int main(){int n,q;cin>>n>>q;vector<int> v(n);for(int i=0; i<n; i++) cin>>v[i];SegmentTreeSum STs(v);for(int i=0; i<q; i++){int a,b;cin >> a >> b;cout << STs.rangeSum(a-1,b) << endl;}}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
8 36 7 6 4 6 2 9 4 8 1 1 1 2 1 3 ... |
correct output |
---|
7 1 5 3 1 ... |
user output |
---|
7 1 5 3 1 ... |
Test 2
Verdict: ACCEPTED
input |
---|
200000 200000 921726510 307633388 992247073 ... |
correct output |
---|
834756431 130379787 403037296 308618218 784778243 ... |
user output |
---|
834756431 130379787 403037296 308618218 784778243 ... Truncated |