fork download
copy 
  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define MOD 1000000007
  5. #define ft first
  6. #define sd second
  7. #define VI vector<int>
  8. #define VLL vector<long long int>
  9. #define PII pair<int,int>
  10. #define pb push_back
  11. #define rsz(v,n) v.resize(n)
  12. // input and output
  13. #define scan(x) scanf("%d",&x)
  14. #define scanll(x) scanf("%lld",&x)
  15. #define ll long long int
  16. #define rep(i,x,y) for(i=x;i<y;i++)
  17. #define print(x) printf("%d\n",x)
  18. #define printll(x) printf("%lld\n",x)
  19. #define all(v) v.begin(),v.end()
  20. #define ms(v) memset(v,0,sizeof(v))
  21. #define FOR(i,a,b)  for(i=a;i<b;i++)
  22. struct node{
  23. 	int bit[22];
  24. 	bool bit_mask[22];
  25. 	bool flag;
  26. 	ll sum;
  27. 	int count;
  28. 	node(){
  29. 		memset(bit,0,sizeof(bit));
  30. 		memset(bit_mask,0,sizeof(bit_mask));
  31. 		sum=0;
  32. 	    flag=0;
  33. 	}
  34. };
  35. vector<node>st;
  36. VI arr;
  37.  
  38. void buildst(int idx,int ss,int se){
  39.  
  40. 	if(ss==se){
  41. 		for(int i=0;i<21;i++)
  42. 		{
  43. 			if(((1<<i)&arr[se]))
  44. 			 st[idx].bit[i]=true;
  45. 			else
  46. 			 st[idx].bit[i]=false;
  47. 		}
  48. 		return;
  49. 	}
  50. 	int mid=(ss+se)>>1;
  51. 	buildst(2*idx+1,ss,mid);
  52. 	buildst(2*idx+2,mid+1,se);
  53. 	for(int i=0;i<=21;i++) st[idx].bit[i]=st[idx*2+1].bit[i]+st[idx*2+2].bit[i];
  54. }
  55.  
  56. void adjust(int idx,int ss,int se){
  57.  
  58. 		int mid=(ss+se)>>1;
  59. 		for(int i=0;i<=21;i++)
  60. 		{
  61. 			int x=st[idx].bit_mask[i];
  62. 			if(x){
  63. 				st[2*idx+1].bit[i]=mid-ss+1-st[2*idx+1].bit[i];
  64. 				if(st[idx*2+1].bit_mask[i]){
  65. 				  st[idx*2+1].bit_mask[i]=0;
  66. 				}else{
  67. 				  st[idx*2+1].bit_mask[i]=1;
  68. 				}
  69. 			}else{
  70. 				if(st[idx*2+1].bit_mask[i]){
  71. 				    st[idx*2+1].bit_mask[i]=1;	
  72. 				}else{
  73. 				    st[idx*2+1].bit_mask[i]=0;	
  74. 				}
  75. 			}
  76. 			if(x){
  77. 				st[2*idx+2].bit[i]=se-mid-st[2*idx+2].bit[i];
  78. 				if(st[idx*2+2].bit_mask[i]){
  79. 				  st[idx*2+2].bit_mask[i]=0;
  80. 				}else{
  81. 				  st[idx*2+2].bit_mask[i]=1;
  82. 				}
  83. 			}else{
  84. 				if(st[idx*2+2].bit_mask[i]){
  85. 				    st[idx*2+2].bit_mask[i]=1;	
  86. 				}else{
  87. 				    st[idx*2+2].bit_mask[i]=0;	
  88. 				}
  89. 			}
  90. 		}
  91. 		st[idx*2+1].flag=1;
  92. 		st[idx*2+2].flag=1;
  93. 		st[idx].flag=0;
  94. 		for(int i=0;i<=21;i++) st[idx].bit_mask[i]=0;
  95. }
  96.  
  97. void update(int idx,int ss,int se,int l,int r,int x)
  98. {
  99. 	if(ss>r||l>se) return;
  100.  
  101. 	if(l<=ss&&se<=r){
  102. 		for(int i=0;i<=21;i++){
  103. 			if(x&(1<<i)){		
  104. 				st[idx].bit[i]=se-ss+1-st[idx].bit[i];
  105. 				if(st[idx].bit_mask[i]){
  106. 				  st[idx].bit_mask[i]=0;
  107. 				}else{
  108. 				  st[idx].bit_mask[i]=1;
  109. 				}
  110. 			}else{
  111. 				if(st[idx].bit_mask[i]){
  112. 				    st[idx].bit_mask[i]=1;	
  113. 				}else{
  114. 				    st[idx].bit_mask[i]=0;	
  115. 				}
  116. 			}
  117. 		}
  118. 		st[idx].flag=true;
  119. 		return;
  120. 	}
  121. 	int mid=(ss+se)>>1;
  122. 	if(st[idx].flag) adjust(idx,ss,se);
  123.     update(2*idx+1,ss,mid,l,r,x);	
  124.     update(2*idx+2,mid+1,se,l,r,x);
  125. 	for(int i=0;i<=21;i++) st[idx].bit[i]=st[idx*2+1].bit[i]+st[idx*2+2].bit[i];
  126. }
  127. ll query(int idx,int ss,int se,int l,int r)
  128. {
  129. 	if(l>se||r<ss) return 0;
  130. 	ll sum;
  131. 	if(l<=ss&&se<=r)
  132. 	{
  133. 		sum=0;
  134. 		for(int i=0;i<=21;i++)
  135. 		 sum+=((1<<i)*st[idx].bit[i]);
  136. 		return sum;
  137. 	}
  138. 	if(st[idx].flag) adjust(idx,ss,se);
  139. 	int mid=(ss+se)>>1;
  140. 	return query(2*idx+1,ss,mid,l,r)+query(2*idx+2,mid+1,se,l,r);
  141. }
  142. int main()
  143. {
  144.  int n;
  145.  scan(n);
  146.  int size=(ceil)(log2(n))+1;
  147.  size++;
  148.  st.resize(1<<size);
  149.  arr.resize(n);
  150.  for(int i=0;i<n;i++) cin>>arr[i]; 
  151.  buildst(0,0,n-1);
  152.  int q;
  153.  scan(q);
  154.  int l,r,x,type;
  155.  while(q--)
  156.  {
  157.  	scan(type);
  158.  	scan(l);
  159.  	scan(r);
  160.  	l--;
  161.  	r--;
  162.  	if(type==2){
  163.  		scan(x);
  164.  		update(0,0,n-1,l,r,x);
  165.  	}else{
  166.  		cout<<query(0,0,n-1,l,r)<<endl;
  167.  	}
  168.  }
  169.  return 0;
  170. }
  171.  
Runtime error #stdin #stdout #stderr 0s 3476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_default_append
https://ideone.com/0OuZRq
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

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!