Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- typedef long long ll;
- class Solution{
- public:
- vector<int> segment_tree;
- vector<int> v;
- void build(int L, int R, int pos) {
- if(L == R) {
- segment_tree[pos] = v[L];
- }
- else {
- int middle = (L + R) / 2;
- build(L, middle, 2 * pos);
- build(middle + 1, R, 2 * pos + 1);
- segment_tree[pos] = segment_tree[2 * pos] ^ segment_tree[2 * pos + 1];
- }
- }
- int query(int L, int R, int pos, int i, int j) {
- // L R i L R j L R
- if(i <= L and R <= j) {
- return segment_tree[pos];
- }
- if(R < i or j < L) {
- return 0;
- }
- int middle = (L + R) / 2;
- return query(L, middle, 2 * pos, i, j) ^ query(middle + 1, R, 2 * pos + 1, i, j);
- }
- vector<int> specialXor(int N, int Q, int a[], vector<int> q[])
- {
- segment_tree.resize(4 * N);
- v.resize(N);
- for(int i = 0; i < N; i++) {
- v[i] = a[i];
- }
- build(0, N - 1, 1);
- vector<int> ret;
- for(int i = 0; i < Q; i++) {
- int si = q[i][0] - 1, sj = q[i][1] - 1;
- ll res = query(0, N - 1, 1, 0, si - 1);
- res ^= query(0, N - 1, 1, sj + 1, N - 1);
- ret.push_back(res);
- }
- return ret;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement