fork download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int SIZE = 1<<17;
  7. const int TREE_SIZE = SIZE<<2;
  8.  
  9. struct Node {
  10.   int a0,a1,a2;
  11. };
  12.  
  13. int n;
  14. int q;
  15. int type,a,b;
  16. int i;
  17. Node tree[TREE_SIZE];
  18. int lazy[TREE_SIZE];
  19.  
  20. void build_tree(int a, int b, int node) {
  21.   if(a>b) return;
  22.   if(a==b) {
  23.     tree[node].a0=1;
  24.     tree[node].a1=0;
  25.     tree[node].a2=0;
  26.     return;
  27.   }
  28.   tree[node].a0=b-a+1;
  29.   tree[node].a1=0;
  30.   tree[node].a2=0;
  31.   build_tree(a,(a+b)>>1,node<<1);
  32.   build_tree(((a+b)>>1)+1,b,(node<<1)|1);
  33. }
  34.  
  35. void update_tree(int a, int b, int i, int j, int node) {
  36.   while(lazy[node]>0) {
  37.     lazy[node]--;
  38.     //printf("%d\n", lazy[node]);
  39.     int tmp=tree[node].a0;
  40.     tree[node].a0=tree[node].a2;
  41.     tree[node].a2=tree[node].a1;
  42.     tree[node].a1=tmp;
  43.     if(a!=b) {
  44.       lazy[node<<1]=(lazy[node<<1]+1)%3;
  45.       lazy[(node<<1)|1]=(lazy[(node<<1)|1]+1)%3;
  46.     }
  47.   }
  48.   if(a>b || a>j || b<i) return;
  49.   if(a>=i && b<=j) {
  50.     int tmp=tree[node].a0;
  51.     tree[node].a0=tree[node].a2;
  52.     tree[node].a2=tree[node].a1;
  53.     tree[node].a1=tmp;
  54.     if(a!=b) {
  55.       lazy[node<<1]=(lazy[node<<1]+1)%3;
  56.       lazy[(node<<1)|1]=(lazy[(node<<1)|1]+1)%3;
  57.     }
  58.     return; 
  59.   }
  60.   update_tree(a,(a+b)>>1,i,j,node<<1);
  61.   update_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1);
  62.   tree[node].a0=tree[node<<1].a0+tree[(node<<1)|1].a0;
  63.   tree[node].a1=tree[node<<1].a1+tree[(node<<1)|1].a1;
  64.   tree[node].a2=tree[node<<1].a2+tree[(node<<1)|1].a2;
  65. }
  66.  
  67. int query_tree(int a, int b, int i, int j, int node) {
  68.   if(a>b || b<i || a>j) return 0;
  69.   while(lazy[node]>0) {
  70.     lazy[node]--;
  71.     int tmp=tree[node].a0;
  72.     tree[node].a0=tree[node].a2;
  73.     tree[node].a2=tree[node].a1;
  74.     tree[node].a1=tmp;
  75.     if(a!=b) {
  76.       lazy[node<<1]=(lazy[node<<1]+1)%3;
  77.       lazy[(node<<1)|1]=(lazy[(node<<1)|1]+1)%3;
  78.     }
  79.   }
  80.   if(a>=i && b<=j) return tree[node].a0;
  81.   int q1,q2;
  82.   q1=query_tree(a,(a+b)>>1,i,j,node<<1);
  83.   q2=query_tree(((a+b)>>1)+1,b,i,j,(node<<1)|1);
  84.   return q1+q2;
  85. }
  86.  
  87. int main() {
  88.   //ios_base::sync_with_stdio(false);
  89.   //cin.tie(NULL);
  90.   //freopen("test.txt","r",stdin);
  91.  
  92.   scanf("%d %d", &n, &q);
  93.   build_tree(1,n,1);
  94.   for(i=1;i<=q;i++) {
  95.     scanf("%d %d %d", &type, &a, &b);
  96.     a++;
  97.     b++;
  98.     if(type==0) update_tree(1,n,a,b,1);
  99.     else printf("%d\n", query_tree(1,n,a,b,1));
  100.   } 
  101.  
  102.   return 0;
  103. }
Success #stdin #stdout 0s 11288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/rle8iQ
language:
C++14 (gcc 8.3)
created:
9 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!