Advertisement
Josif_tepe

Untitled

Mar 27th, 2024
687
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.35 KB | None | 0 0
  1. typedef long long ll;
  2. class Solution{
  3. public:
  4.     vector<int> segment_tree;
  5.     vector<int> v;
  6.     void build(int L, int R, int pos) {
  7.         if(L == R) {
  8.             segment_tree[pos] = v[L];
  9.         }
  10.         else {
  11.             int middle = (L + R) / 2;
  12.             build(L, middle, 2 * pos);
  13.             build(middle + 1, R, 2 * pos + 1);
  14.             segment_tree[pos] = segment_tree[2 * pos] ^ segment_tree[2 * pos + 1];
  15.         }
  16.     }
  17.     int query(int L, int R, int pos, int i, int j) {
  18.         // L R  i L R j L R
  19.         if(i <= L and R <= j) {
  20.             return segment_tree[pos];
  21.         }
  22.         if(R < i or j < L) {
  23.             return 0;
  24.            
  25.         }
  26.         int middle = (L + R) / 2;
  27.         return query(L, middle, 2 * pos, i, j) ^ query(middle + 1, R, 2 * pos + 1, i, j);
  28.     }
  29.     vector<int> specialXor(int N, int Q, int a[], vector<int> q[])
  30.     {
  31.         segment_tree.resize(4 * N);
  32.         v.resize(N);
  33.         for(int i = 0; i < N; i++) {
  34.             v[i] = a[i];
  35.         }
  36.         build(0, N - 1, 1);
  37.         vector<int> ret;
  38.         for(int i = 0; i < Q; i++) {
  39.             int si = q[i][0] - 1, sj = q[i][1] - 1;
  40.             ll res = query(0, N - 1, 1, 0, si - 1);
  41.             res ^= query(0, N - 1, 1, sj + 1, N - 1);
  42.            
  43.             ret.push_back(res);
  44.         }
  45.         return ret;
  46.     }
  47. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement