fork download
copy 
  1. //============================================================================
  2. // Name        : SPOJ Multiple by 3 (Segment Tree)
  3. // Author      : Tarango Khan
  4. // Copyright   : Team Byteheads
  5. // Description : !!!Hello World!!!
  6. //============================================================================
  7.  
  8. #include <bits/stdc++.h>
  9. using namespace std;
  10. #define Size 100005
  11.  
  12. struct vert{
  13.     int cnt[3];
  14.     int prop;
  15.     vert(){
  16.         cnt[0] = cnt[1] = cnt[2] = prop = 0;
  17.     }
  18. };
  19. vert tree[Size*4];
  20.  
  21. void build_tree(int cur,int Start,int End){
  22.     if(Start == End){
  23.         tree[cur].cnt[0] = 1;
  24.         tree[cur].cnt[1] = 0;
  25.         tree[cur].cnt[2] = 0;
  26.         tree[cur].prop = 0;
  27.         return;
  28.     }
  29.     int left = cur*2;
  30.     int right = left+1;
  31.     int mid = (Start+End)/2;
  32.     build_tree(left,Start,mid);
  33.     build_tree(right,mid+1,End);
  34.     tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
  35.     tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
  36.     tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
  37.     tree[cur].prop = tree[left].prop + tree[right].prop;
  38. }
  39.  
  40. void update_prop(int cur){
  41.     int tmp = tree[cur].cnt[2];
  42.     tree[cur].cnt[2] = tree[cur].cnt[1];
  43.     tree[cur].cnt[1] = tree[cur].cnt[0];
  44.     tree[cur].cnt[0] = tmp;
  45. }
  46.  
  47. void update_tree(int cur,int Start,int End,int u,int v){
  48.     if(End<u || Start>v) return;
  49.     if(Start>=u && End<=v){
  50.         update_prop(cur);
  51.         tree[cur].prop += 1;
  52.         return;
  53.     }
  54.     int left = cur*2;
  55.     int right = left+1;
  56.     int mid = (Start+End)/2;
  57.     update_tree(left,Start,mid,u,v);
  58.     update_tree(right,mid+1,End,u,v);
  59.     tree[cur].cnt[0] = tree[left].cnt[0] + tree[right].cnt[0];
  60.     tree[cur].cnt[1] = tree[left].cnt[1] + tree[right].cnt[1];
  61.     tree[cur].cnt[2] = tree[left].cnt[2] + tree[right].cnt[2];
  62. }
  63.  
  64. vert tree_query(int cur,int Start,int End,int u,int v,int carry){
  65.     vert newV;
  66.     if(End<u || Start>v){
  67.         newV.prop = -1;
  68.         return newV;
  69.     }
  70.     if(Start>=u && End<=v){
  71.         newV.cnt[0] = tree[cur].cnt[0];
  72.         newV.cnt[1] = tree[cur].cnt[1];
  73.         newV.cnt[2] = tree[cur].cnt[2];
  74.         newV.prop = tree[cur].prop;
  75.         for(int s = 0;s<carry;s++){
  76.         	int tmp = newV.cnt[2];
  77.         	newV.cnt[2] = newV.cnt[1];
  78.         	newV.cnt[1] = newV.cnt[0];
  79.         	newV.cnt[0] = tmp;
  80.         }
  81.         return newV;
  82.     }
  83.     int left = cur*2;
  84.     int right = left+1;
  85.     int mid = (Start+End)/2;
  86.     vert left_ret = tree_query(left,Start,mid,u,v,carry + tree[cur].prop);
  87.     vert right_ret = tree_query(right,mid+1,End,u,v,carry + tree[cur].prop);
  88.     if(left_ret.prop == -1) return right_ret;
  89.     if(right_ret.prop == -1) return left_ret;
  90.     newV.cnt[0] = left_ret.cnt[0] + right_ret.cnt[0];
  91.     newV.cnt[1] = left_ret.cnt[1] + right_ret.cnt[1];
  92.     newV.cnt[2] = left_ret.cnt[2] + right_ret.cnt[2];
  93.     return newV;
  94. }
  95.  
  96. int main() {
  97.     int N,Q,u,v,type;
  98. 	scanf("%d %d",&N,&Q);
  99. 	build_tree(1,1,N);
  100. 	for(int i = 1;i<=Q;i++){
  101. 		scanf("%d",&type);
  102. 		if(type == 0){
  103. 			scanf("%d %d",&u,&v);
  104. 			u++;v++;
  105. 			update_tree(1,1,N,u,v);
  106. 		}else{
  107. 			scanf("%d %d",&u,&v);
  108. 			u++;v++;
  109. 			vert sum = tree_query(1,1,N,u,v,0);
  110. 			printf("%d\n",sum.cnt[0]);
  111. 		}
  112. 	}
  113. }
  114.  
Success #stdin #stdout 0s 9392KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout
copy 
4
1
0
2
https://ideone.com/7MaAlr
language:
C++14 (gcc 8.3)
created:
9 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!