Task: | Xor sum |
Sender: | arnxxau |
Submission time: | 2024-09-23 16:24:06 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.61 s | details |
Code
#include <climits>#include <iostream>#include <vector>// Clase para manejar sumas de segmentosclass SumSegmentTree {private:std::vector<int> tree;std::vector<int> data;int n;void build(int node, int start, int end) {if (start == end) {tree[node] = data[start];} else {int mid = (start + end) / 2;build(2 * node + 1, start, mid);build(2 * node + 2, mid + 1, end);tree[node] = tree[2 * node + 1] ^ tree[2 * node + 2];}}int query(int node, int start, int end, int l, int r) {if (r < start || l > end) {return 0;}if (l <= start && end <= r) {return tree[node];}int mid = (start + end) / 2;return query(2 * node + 1, start, mid, l, r) ^ query(2 * node + 2, mid + 1, end, l, r);}void update(int node, int start, int end, int idx, int value) {if (start == end) {data[idx] = value;tree[node] = value;} else {int mid = (start + end) / 2;if (start <= idx && idx <= mid) {update(2 * node + 1, start, mid, idx, value);} else {update(2 * node + 2, mid + 1, end, idx, value);}tree[node] = tree[2 * node + 1] + tree[2 * node + 2];}}public:SumSegmentTree(const std::vector<int>& initial_data) : data(initial_data) {n = initial_data.size();tree.resize(4 * n);build(0, 0, n - 1);}int sum(int l, int r) {return query(0, 0, n - 1, l, r);}void update(int idx, int value) {update(0, 0, n - 1, idx, value);}};using namespace std;int main() {int n, q;cin >> n >> q;vector<int> arr(n);for (int i = 0; i < n; i++) {cin >> arr[i];}SumSegmentTree t(arr);for (int i = 0; i < q; i++) {int a, b;cin >> a >> b;cout << t.sum(a - 1, b - 1) << 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 |