apl-mhd

lazy segment

Nov 28th, 2019
189
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. #define  maxSize  100010
  5. using namespace std;
  6. int arr[maxSize] = {0};
  7.  
  8.  
  9.  
  10. struct  info{
  11.  
  12.     int sum = 0;
  13.     int divSum = 0;
  14.     int  prop = 0;
  15.  
  16.  
  17.  
  18. }tree[maxSize * 3];
  19.  
  20.  
  21.  
  22. void init(int node, int b, int e){
  23.  
  24.     if(b == e){
  25.  
  26.         tree[node].sum = 0;
  27.         tree[node].divSum = 1;
  28.         tree[node].prop = 0;
  29.         return;
  30.     }
  31.  
  32.     int l = node * 2 + 1;
  33.     int r = node * 2 + 2;
  34.     int m = ( b + e ) / 2;
  35.  
  36.     init(l, b, m);
  37.     init(r, m+1, e);
  38.  
  39.     //tree[node].divSum = tree[l].divSum + tree[r].divSum;
  40.     tree[node].sum = 1;
  41.  
  42. }
  43.  
  44.  
  45. void  update(int node, int b, int e, int i, int j, int carry=0){
  46.  
  47.  
  48.         if( j<b || i > e ){
  49.  
  50.             return;
  51.         }
  52.  
  53.         if(b>=i && e<=j){
  54.  
  55.                tree[node].sum +=1;
  56.  
  57.                //int a = (tree[node].sum + carry) % 3;
  58.  
  59.                //tree[node].divSum = ((tree[node].sum % 3 == 0)? (e-b + 1): 0);
  60.             //tree[node].divSum =  (a == 0)? (e-b+1) : 0;
  61.  
  62.             return;
  63.         }
  64.  
  65.         int l = node * 2 + 1;
  66.         int r = node * 2 + 2;
  67.         int m = ( b + e ) / 2;
  68.         update(l, b, m, i, j, carry+tree[node].sum);
  69.         update(r, m+1, e, i, j, carry+tree[node].sum);
  70.  
  71.         int lsum = (tree[l].sum + carry) %3;
  72.         int rsum = tree[r].sum + carry;
  73.  
  74.         //tree[node].divSum = (lsum % 3) + tree[r].divSum ;
  75.  
  76.         //tree[node].divSum = tree[l].divSum + tree[r].divSum ;
  77.  
  78.  
  79. }
  80.  
  81.  
  82.  
  83.  
  84. int query(int node, int b, int e, int i, int j, int carry = 0){
  85.  
  86.         if(j< b || i > e)
  87.             return  0;
  88.  
  89.         if(b >= i && e<=j){
  90.  
  91.             if(b == e)
  92.                 return ((carry % 3 == 0 ) ? 1:0 );
  93.  
  94.             else
  95.                 //return ((tree[node].sum + carry) % 3 == 0 )? (e - b + 1): 0;
  96.                 return ((tree[b].sum + carry) % 3 == 0 )? (e - b + 1): 0;
  97.         }
  98.  
  99.  
  100.  
  101.         int l = node * 2 + 1;
  102.         int r = node * 2 + 2;
  103.         int m = (b + e) / 2;
  104.         return query(l, b, m, i, j, carry + tree[node].sum) + query(r, m+1, e, i, j, carry + tree[node].sum) ;
  105.  
  106. }
  107.  
  108.  
  109. int main() {
  110.  
  111.  
  112.  
  113.     init(0, 0, 3);
  114.     update(0, 0, 3, 0, 3);
  115.     update(0, 0, 3, 0, 3);
  116.     update(0, 0, 3, 0, 3);
  117.     update(0, 0, 3, 0, 0);
  118.  
  119.  
  120.  
  121.     cout<<tree[0].sum<<endl<<endl;
  122.  
  123.  
  124.      //update(0, 0, 3, 1, 1);
  125.      //update(0, 0, 3, 1, 1);
  126.      //
  127.     cout<<query(0, 0, 3, 1, 1)<<endl;
  128.     cout<<query(0, 0, 3, 0, 1)<<endl;
  129.     cout<<query(0, 0, 3, 0, 0)<<endl;
  130.     cout<<query(0, 0, 3, 1, 3)<<endl;
  131.     cout<<query(0, 0, 3, 2, 3)<<endl;
  132.     cout<<query(0, 0, 3, 2, 2)<<endl;
  133.     cout<<query(0, 0, 3, 0, 3)<<endl;
  134.  
  135.  
  136.      /*cout<<tree[3].sum<<endl;
  137.      cout<<tree[4].sum<<endl;
  138.      cout<<tree[5].sum<<endl;
  139.      cout<<tree[6].sum<<endl;*/
  140.  
  141.  
  142.     /* for (int i = 0; i <7; ++i) {
  143.          //cout<<tree[i].divSum<<endl;
  144.      }
  145.  
  146. */
  147.     int n, q;
  148.  
  149.     scanf("%d%d",&n, &q);
  150.     init(0, 0, n-1);
  151.  
  152.  
  153.     for (int i = 0; i < q ; ++i) {
  154.  
  155.         int a,b,c;
  156.  
  157.         scanf("%d%d%d",&a, &b, &c);
  158.         if(a==1)
  159.  
  160.             printf("%d\n",query(0, 0, n-1, b, c));
  161.  
  162.         else
  163.  
  164.             update(0, 0, n-1, b,c);
  165.     }
  166.  
  167.  
  168.     return 0;
  169. }
RAW Paste Data