fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long 
  3. #define mp make_pair 
  4. #define f(i,n) for(int i=0;i<n;i++) 
  5. #define F first 
  6. #define S second 
  7. #define pb push_back 
  8.  
  9. using namespace std;
  10.  
  11. void build_segment_tree(ll arr[],ll tree[],ll n)
  12. {
  13.     for(int i=0;i<n;i++)
  14.     {
  15.         tree[n+i]=arr[i];
  16.     }
  17.  
  18.     for(int i=n-1; i>0 ;i--)
  19.     {
  20.         tree[i]=tree[2*i]^tree[(2*i)+1];
  21.     }
  22. }
  23.  
  24. // update arr[index]=arr[index]^value, and make changes accordingly to the segment tree
  25. void update_segment_tree(int index,ll value,ll n,ll tree[])
  26. {
  27.     tree[index+n]=tree[index+n]^value;
  28.     index=index+n;
  29.  
  30.     for(int i=index;i>=1;i=i/2)
  31.     {
  32.         tree[i/2]=tree[i]^tree[i^1];
  33.     }
  34. }
  35.  
  36. // query for interval [l,r)
  37. ll query(int l,int r,ll tree[],ll n)
  38. {
  39.     ll res=0LL;
  40.     for(l=l+n,r=r+n;l<r;l=l/2,r=r/2)
  41.     {
  42.         if(l%2==1)
  43.         {
  44.             res=res^tree[l++];
  45.         }
  46.         if(r%2==1)
  47.         {
  48.             res=res^tree[--r];
  49.         }
  50.     }
  51.     return res;
  52. }
  53.  
  54. void test(){
  55. 	ll n,q;
  56. 	cin>>n>>q;
  57. 	ll arr[n];
  58. 	f(i,n)cin>>arr[i];
  59. 	ll tree[2*n];
  60. 	build_segment_tree(arr,tree,n);
  61. 	while(q--){
  62. 		ll t,x,y;
  63. 		cin>>t>>x>>y;
  64. 		if(t==1){
  65. 			update_segment_tree(x-1,y,n,tree);
  66. 		}else{
  67. 			ll qu = query(x-1,y,tree,n);
  68. 			cout<<qu<<"\n";
  69. 		}
  70. 	}
  71. }
  72.  
  73. int main(){
  74. 	std::ios::sync_with_stdio(false);
  75. 	cin.tie(0);
  76. 	cout.tie(0);
  77. 	int tests=1;
  78. 	// cin>>tests;
  79. 	while(tests--){
  80. 		test();
  81. 	}
  82. }
  83.  
Success #stdin #stdout 0s 4992KB
comments (?)
stdin
copy 
3 4
1 2 3
2 1 3
2 2 3
1 2 3
2 2 3
stdout
copy 
0
1
2
https://ideone.com/wmMMXE
language:
C++14 (gcc 8.3)
created:
3 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!