fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. long long int tree[300000][3],lazy[300000],A[300000];
  4. using namespace std;
  5. void build(ll int node,ll int start,ll int end)
  6. {
  7.     if(start == end)
  8.     {
  9.         tree[node][0] = 1, tree[node][1] = 0, tree[node][2] = 0;
  10.     }
  11.     else
  12.     {
  13.         int mid = (start + end) / 2;
  14.         // Recurse on the left child
  15.         build(2*node, start, mid);
  16.         // Recurse on the right child
  17.         build(2*node+1, mid+1, end);
  18.         // Internal node will have the sum of both of its children
  19.         tree[node][0] = tree[2*node][0] + tree[2*node+1][0];
  20.         tree[node][1] = tree[2*node][1] + tree[2*node+1][1];
  21.         tree[node][2] = tree[2*node][2] + tree[2*node+1][2];
  22.     }
  23. }
  24. void updateRange(ll int node,ll int start,ll int end,ll int l,ll int r)
  25. {
  26.     if(lazy[node] != 0)
  27.     {
  28.         // This node needs to be updated
  29.         lazy[node]+=1;
  30.         if(start != end)
  31.         {
  32.             lazy[node*2]+=lazy[node];       // Mark child as lazy
  33.             lazy[node*2+1]+=lazy[node];
  34.             int rotate=lazy[node]%3;
  35.             for(ll int i=1;i<=rotate;i++)
  36.             {
  37.                 ll int t1=tree[node*2][0];ll int t2=tree[node*2][1];ll int t3=tree[node*2][2];
  38.                 tree[node*2][0]=t3;tree[node*2][1]=t1;tree[node*2][2]=t2;
  39.             }
  40.             for(ll int i=1;i<=rotate;i++)
  41.             {
  42.                 ll int t1=tree[node*2+1][0];ll int t2=tree[node*2+1][1];ll int t3=tree[node*2+1][2];
  43.                 tree[node*2+1][0]=t3;tree[node*2+1][1]=t1;tree[node*2+1][2]=t2;
  44.             }
  45.         }
  46.         lazy[node] = 0;                                  // Reset it
  47.     }
  48.     if(start > end or start > r or end < l)              // Current segment is not within range [l, r]
  49.         return ;
  50.     if(start >= l and end <= r)
  51.     {
  52.         // Segment is fully within range
  53.         //tree[node] =  val;
  54.         //cout<<node<<" "<<tree[node][0]<<endl;
  55.         ll int t1=tree[node][0];ll int t2=tree[node][1];ll int t3=tree[node][2];
  56.         tree[node][0]=t3;tree[node][1]=t1;tree[node][2]=t2;
  57.         //cout<<node<<" "<<tree[node][0]<<endl;
  58.         if(start != end)
  59.         {
  60.             // Not leaf node
  61.             lazy[node*2]+=1;
  62.             lazy[node*2+1]+=1;
  63.         }
  64.         return;
  65.     }
  66.     ll int mid = (start + end) / 2;
  67.     updateRange(node*2, start, mid, l, r);        // Updating left child
  68.     updateRange(node*2 + 1, mid + 1, end, l, r);   // Updating right child
  69.     tree[node][0] = tree[2*node][0] + tree[2*node+1][0];
  70.     tree[node][1] = tree[2*node][1] + tree[2*node+1][1];
  71.     tree[node][2] = tree[2*node][2] + tree[2*node+1][2];
  72.             //cout<<node<<" "<<tree[node][0]<<endl;
  73. }
  74. ll int queryRange(ll int node,ll int start,ll int end,ll int l,ll int r)
  75. {
  76.     if(start > end or start > r or end < l)
  77.         return 0;         // Out of range
  78.     if(lazy[node] != 0)
  79.     {
  80.         // This node needs to be updated
  81.         lazy[node]+=1;
  82.         if(start != end)
  83.         {
  84.             lazy[node*2]+=lazy[node];                  // Mark child as lazy
  85.             lazy[node*2+1]+=lazy[node];
  86.             ll int rotate=lazy[node]%3;
  87.             for(ll int i=1;i<=rotate;i++)
  88.             {
  89.                 ll int t1=tree[node*2][0];ll int t2=tree[node*2][1];ll int t3=tree[node*2][2];
  90.                 tree[node*2][0]=t3;tree[node*2][1]=t1;tree[node*2][2]=t2;
  91.             }
  92.             for(ll int i=1;i<=rotate;i++)
  93.             {
  94.                 ll int t1=tree[node*2+1][0];ll int t2=tree[node*2+1][1];ll int t3=tree[node*2+1][2];
  95.                 tree[node*2+1][0]=t3;tree[node*2+1][1]=t1;tree[node*2+1][2]=t2;
  96.             }
  97.         }
  98.         lazy[node] = 0;                                  // Reset it
  99.     }
  100.     if(start >= l and end <= r)             // Current segment is totally within range [l, r]
  101.         return tree[node][0];
  102.     ll int mid = (start + end) / 2;
  103.     ll int p1 = queryRange(node*2, start, mid, l, r);         // Query left child
  104.     ll int p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
  105.     return p1 + p2;
  106. }
  107. int main()
  108. {
  109.     ll int n,q,type,l,r,i;
  110.     scanf("%lld%lld",&n,&q);
  111.     build(1,1,n);
  112.     /*for(int i=1;i<=2*n;i++)
  113.         cout<<i<<" "<<tree[i][0]<<" "<<tree[i][1]<<" "<<tree[i][2]<<endl;*/
  114.     while(q--)
  115.     {
  116.         scanf("%lld",&type);
  117.         if(type){
  118.             scanf("%lld%lld",&l,&r);l++,r++;printf("%lld\n",queryRange(1,1,n,l,r));
  119.         }
  120.         else{
  121.             scanf("%lld%lld",&l,&r);l++,r++;updateRange(1,1,n,l,r);
  122.         }
  123.     }
  124. }
  125.  
Runtime error #stdin #stdout 0s 14448KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YOnZO6
language:
C++ 4.3.2 (gcc-4.3.2)
created:
7 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!