fork(2) download 
  1. #include <iostream>
  2. #include <cstdio>
  3. using namespace std;
  4. class node
  5. {
  6. public:
  7.         int left_r,right_r,count_0,count_1,count_2,change;
  8.         node *left,*right;
  9.         node() {
  10.                 left_r=right_r=count_0=count_1=count_2=change=0;
  11.                 left=right=NULL;
  12.         }
  13. };
  14. void maketree(int lower , int higher , node *current )
  15. {
  16.         current->count_0=higher-lower+1;
  17.         current->left_r=lower;
  18.         current->right_r=higher;
  19.         if(higher!=lower) {
  20.                 node *leftt=new node();
  21.                 node *rightt=new node();
  22.                 current->left=leftt;
  23.                 current->right=rightt;
  24.                 maketree(lower,(lower+higher)/2,leftt);
  25.                 maketree((lower+higher)/2+1,higher,rightt);
  26.         }
  27. }
  28. void rotate(node *current)
  29. {
  30.         int temp=current->count_2;
  31.         current->count_2=current->count_1;
  32.         current->count_1=current->count_0;
  33.         current->count_0=temp;
  34. }
  35. void copyit(node *copy,node *current)
  36. {
  37.         copy->count_0=current->count_0;
  38.         copy->count_1=current->count_1;
  39.         copy->count_2=current->count_2;
  40.         copy->change=current->change;
  41. }
  42. void add(node *current,node *ch1,node *ch2)
  43. {
  44.         current->count_0=ch1->count_0+ch2->count_0;
  45.         current->count_1=ch1->count_1+ch2->count_1;
  46.         current->count_2=ch1->count_2+ch2->count_2;
  47. }
  48. void get(node *current,node * child1,node *child2)
  49. {
  50.         node *temp1_ch=new node();
  51.         node *temp2_ch=new node();
  52.         copyit(temp1_ch,child1);
  53.         copyit(temp2_ch,child2);
  54.         temp1_ch->change=temp1_ch->change%3;
  55.         temp2_ch->change=temp2_ch->change%3;
  56.         while(temp1_ch->change!=0) {
  57.                 rotate(temp1_ch);
  58.                 temp1_ch->change--;
  59.         }
  60.         while(temp2_ch->change!=0) {
  61.                 rotate(temp2_ch);
  62.                 temp2_ch->change--;
  63.         }
  64.         add(current,temp1_ch,temp2_ch);
  65. }
  66. void IS(node *current)
  67. {
  68.         rotate(current);
  69.         current->change=0;
  70.         if(current->left!=NULL) {
  71.                 current->left->change++;
  72.                 current->right->change++;
  73.         }
  74. }
  75. void updateRMQ(int lower,int higher,node *current)
  76. {
  77.         int mid=(current->left_r+current->right_r)/2;
  78.         if(current->change%3>0) {
  79.                 IS(current);
  80.         }
  81.         if(current->change%3>0) {
  82.                 IS(current);
  83.         }
  84.         if(lower==current->left_r&&higher==current->right_r) {
  85.                 IS(current);
  86.         } else {
  87.                 if(lower>mid) {
  88.                         updateRMQ(lower,higher,current->right);
  89.                 } else if(higher<=mid) {
  90.                         updateRMQ(lower,higher,current->left);
  91.                 } else {
  92.                         updateRMQ(lower,mid,current->left);
  93.                         updateRMQ(mid+1,higher,current->right);
  94.                 }
  95.                 get(current,current->left,current->right);
  96.         }
  97. }
  98. int countRMQ(int lower,int higher,node *current)
  99. {
  100.         int mid=(current->left_r+current->right_r)/2;
  101.         if(current->change%3>0) {
  102.                 IS(current);
  103.         }
  104.         if(current->change%3>0) {
  105.                 IS(current);
  106.         }
  107.         if(lower==current->left_r&&higher==current->right_r) {
  108.                 if(current->change%3>0) {
  109.                         IS(current);
  110.                 }
  111.                 if(current->change%3>0) {
  112.                         IS(current);
  113.                 }
  114.                 //cout<<current->count_0<<endl;
  115.                 return current->count_0;
  116.         } else {
  117.                 if(lower>mid) {
  118.                         return countRMQ(lower,higher,current->right);
  119.                 } else if(higher<=mid) {
  120.                         return countRMQ(lower,higher,current->left);
  121.                 } else {
  122.                         return countRMQ(lower,mid,current->left)+countRMQ(mid+1,higher,current->right);
  123.                 }
  124.         }
  125. }
  126. int main()
  127. {
  128.         int N,Q;
  129.         //cin>>N>>Q;
  130.         scanf("%d%d",&N,&Q);
  131.         node *top=new node();
  132.         maketree(0,N-1,top);
  133.         while(Q--) {
  134.                 int query,lower,higher;
  135.                 scanf("%d%d%d",&query,&lower,&higher);
  136.                 //cin>>query>>lower>>higher;
  137.                 if(query) {
  138.                         printf("%d\n",countRMQ(lower,higher,top));
  139.                         //cout<<countRMQ(lower,higher,top)<<endl;
  140.                         //cout<<top->left->count_0<<"\t"<<top->left->count_1<<"\t"<<top->left->count_2<<"\t"<<top->left->change<<endl;
  141.                         //cout<<top->right->count_0<<"\t"<<top->right->count_1<<"\t"<<top->right->count_2<<"\t"<<top->right->change<<endl;
  142.                 } else {
  143.                         updateRMQ(lower,higher,top);
  144.                 }
  145.         }
  146.         return 0;
  147. }
Success #stdin #stdout 0s 3036KB
comments (?)
stdin 
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout 
4
1
0
2
https://ideone.com/M1EJD9
language:
C++ (gcc 8.3)
created:
11 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!