fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. const int MAX=(1<<17);
  5. //segment tree array of size 2*max_input_array_size
  6. int sgt[MAX*2];
  7. //build our segment tree iteratively
  8. void build(int n){
  9.     //boolean to check if current operation should be OR or XOR
  10.     bool flag=false;
  11.     //build internal nodes i.e, other than leaf nodes
  12.     for(int i=n-1;i>=1;i--){
  13.         //if this node's index+1 is a power of 2 then our level is changed in tree so we have to change flag to change operation.
  14.         if(!((i+1)&(i))){
  15.             flag=!flag;
  16.         }
  17.         //if flag is true then we have to perform OR
  18.         if(flag){
  19.         //storing OR of child in parent
  20.         sgt[i]=(sgt[2*i]) | (sgt[2*i+1]);
  21.         }
  22.         //if flag is false then we have to perform XOR
  23.         else{
  24.             //storing XOR of child in parent
  25.         sgt[i]=(sgt[2*i]) ^ (sgt[2*i+1]);
  26.         }
  27.     }
  28. }
  29. //function to query the single value which is left after performing every iteration mentioned in problem
  30. int query(int l, int r, int n)
  31. {
  32.     //change original index to segment tree based indexing
  33.     l+=n;
  34.     r+=n;
  35.     //initialise ans to 0
  36.     int sum=0;
  37.     //put flag true initially to have OR operation first
  38.     bool flag=true;
  39.     while(l<=r)
  40.     {
  41.         //if left boundary is a right child(i.e, odd index) then perform operation on this node and move to right of it's parent
  42.         if(l&1)
  43.         {
  44.             //if flag true then OR
  45.             if(flag)
  46.             sum= sum|sgt[l];
  47.             //otherwise XOR
  48.             else
  49.             sum= sum^sgt[l];
  50.             //increment left boundary
  51.             l++;
  52.         }
  53.  
  54.         //if right boundary is a left child(i.e, even index) then perform operation on this node and move to left of it's parent
  55.         if(!(r&1))
  56.         {
  57.             //if flag true then OR
  58.             if(flag)
  59.             sum=sum|sgt[r];
  60.             //otherwise XOR
  61.             else
  62.             sum= sum^sgt[l];
  63.             //decrement right boundary
  64.             r--;
  65.         }
  66.         //move up to previous level
  67.         l=l>>1;//l=l/2;
  68.         r=r>>1;//r=r/2;
  69.  
  70.         //change operation as level is changed in segment tree
  71.         flag=!flag;
  72.     }
  73.     //return answer
  74.     return sum;
  75. }
  76.  
  77. //function to update a given element with index in in original array with value in segment tree
  78. void update(int in, int n,int value)
  79. {
  80.     //change original index to segment tree based indexing
  81.     in+=n;
  82.     //update it's value in segment tree
  83.     sgt[in]=value;
  84.  
  85.     //initially flag true i.e, operation OR to be performed
  86.     bool flag=true;
  87.  
  88.     while(in>1)
  89.     {
  90.         //move to it's parent and update it.
  91.         in=in>>1;//in=in/2;
  92.  
  93.         //if flag true then OR
  94.         if(flag)
  95.         sgt[in] = sgt[in*2]|sgt[in*2+1];
  96.  
  97.         //otherwise XOR
  98.         else
  99.         sgt[in] = sgt[in*2]^sgt[in*2+1];
  100.         //change operation as level in segment tree is changed
  101.         flag=!flag;
  102.     }
  103.     return;
  104. }
  105. //driver function
  106. int32_t main() {
  107.     ios_base::sync_with_stdio(0);
  108.     cin.tie(0);
  109.  
  110.     //2^n is size of the array and q is number of queries
  111.     int n,q;
  112.     cin>>n>>q;
  113.     //size of array
  114.     int sz=(1<<n);
  115.  
  116.     int arr[sz];
  117.  
  118.     for(int i=0;i<sz;i++)
  119.     {
  120.         cin>>arr[i];
  121.         //put array element into leaf of segment tree
  122.         sgt[sz+i]=arr[i];
  123.     }
  124.  
  125.     //build segment tree
  126.     build(sz);
  127.  
  128.     //process all queries
  129.     while(q--){
  130.         //input index and value to be updated with
  131.         int in,val;
  132.         cin>>in>>val;
  133.         //decrement index as input is 1-based and our array indexing is 0 based. 
  134.         in--;
  135.         //call update to update the segment tree
  136.         update(in,sz,val);
  137.         //print element left after all iterations as mentioned in problem
  138.         cout<<query(0,sz-1,sz)<<"\n";
  139.     }
  140.     return 0;
  141. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
2 4
1 6 3 5
1 4
3 4
1 2
1 2
stdout
copy 
1
3
3
3
https://ideone.com/CISlfP
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!