fork download
copy 
  1. //segment trees
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define maxi 500005
  5. #define ll long long
  6. int st[maxi];
  7. ll arr[maxi/5+5];
  8. void init(int lo,int hi,int idx){
  9. 	if(lo==hi){
  10. 		st[idx]=(arr[lo]&(arr[lo]-1))?0:1;
  11. 		return ;
  12. 		}
  13. 	init(lo,((lo+hi)>>1),2*idx);
  14. 	init(((lo+hi)>>1)+1,hi,2*idx+1);
  15. 	st[idx]=st[2*idx]+st[2*idx+1];
  16. 	}
  17. int query(int lo,int hi,int x,int y,int idx){
  18. 	if(x>hi || y<lo || lo>hi)return 0;
  19. 	if(lo>=x && hi<=y){
  20. 		return st[idx];
  21. 		}
  22. 	int mid=(lo+hi)>>1;
  23. 	int t1=query(lo,mid,x,y,2*idx);
  24. 	int t2=query(mid+1,hi,x,y,2*idx+1);
  25. 	return t1+t2;
  26. 	}
  27. void update(int lo,int hi,int x,int y,int z,int idx){
  28. 	if(x>hi || y<lo || lo>hi)return ;
  29. 	if(lo==x && hi==y){
  30. 		st[idx]= (y-x+1)*((z&(z-1))?0:1);
  31. 		return;
  32. 		}
  33. 	int mid=(lo+hi)>>1;
  34. 	if(mid>=y)update(lo,mid,x,y,z,2*idx);
  35. 	else if(x>mid)update(mid+1,hi,x,y,z,2*idx+1);
  36. 	else{
  37. 		update(lo,mid,x,mid,z,2*idx);
  38. 		update(mid+1,hi,mid+1,y,z,2*idx+1);
  39. 		}
  40. 	st[idx]=st[2*idx]+st[2*idx+1];
  41. 	}
  42. int main(){
  43. 	int n,q,i;
  44. 	scanf("%d%d",&n,&q);
  45. 	//ll ele;
  46. 	for(i=1;i<=n;i++){
  47. 		scanf("%lld",&arr[i]);
  48. 		}
  49. 	init(1,n,1);
  50. 	//for(i=0;i<10;i++)cout<<st[i]<<" ";
  51. 	while(q--){
  52. 		int t,x,y,z;
  53. 		scanf("%d%d%d",&t,&x,&y);
  54. 		x++;y++;
  55. 		if(t==1){//query
  56. 			printf("%d\n",query(1,n,x,y,1));
  57. 			}
  58. 		else{//upd
  59. 			scanf("%d",&z);
  60. 			update(1,n,x,y,z,1);
  61. 			}
  62. 		}
  63. 	return 0;
  64. 	}
  65.  
Success #stdin #stdout 0s 6192KB
comments (?)
stdin
copy 
5 3
1 9 13 4 11
1 0 3
0 1 3 7
1 0 3
stdout
copy 
2
1
https://ideone.com/qMQKVP
language:
C++ (gcc 8.3)
created:
8 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!