Advertisement
Josif_tepe

Untitled

Feb 27th, 2023
565
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.30 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <set>
  4. #include <map>
  5. #include <cstring>
  6. #include <algorithm>
  7. #include <stack>
  8. #include <queue>
  9. using namespace std;
  10.  
  11. const int MAX=2e5;
  12.  
  13. int n, q, niza[MAX + 1];
  14. int segment_tree[3 * MAX + 1];
  15.  
  16. void build_tree(int L, int R, int position) {
  17.     if(L == R) {
  18.         segment_tree[position] = niza[L];
  19.     }
  20.     else {
  21.         int middle = (L + R) / 2;
  22.         build_tree(L, middle, 2 * position);
  23.         build_tree(middle + 1, R, 2 * position + 1);
  24.         segment_tree[position] = segment_tree[2 * position] ^ segment_tree[2 * position + 1];
  25.     }
  26. }
  27. int query(int L, int R, int position, int i, int j) {
  28.     // L R i L R j L R
  29.     if(i <= L and R <= j) {
  30.         return segment_tree[position];
  31.     }
  32.     if(R < i or j < L) {
  33.         return 0;
  34.     }
  35.     int middle = (L + R) / 2;
  36.     return query(L, middle, 2 * position, i, j) ^ query(middle + 1, R, 2 * position + 1, i, j);
  37. }
  38.  
  39. int main() {
  40.     ios_base::sync_with_stdio(false);
  41.     cin.tie(0);
  42.    
  43.     cin >> n >> q;
  44.     for (int i = 0; i < n; ++i) {
  45.         cin >> niza[i];
  46.     }
  47.     build_tree(0, n - 1, 1);
  48.    
  49.     for(int i = 0; i < q; i++) {
  50.         int a, b;
  51.         cin >> a >> b;
  52.         a--; b--;
  53.        
  54.         cout << query(0, n - 1, 1, a, b) << endl;
  55.     }
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement