SHARE
TWEET

Untitled

a guest Dec 12th, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int carry[400025][3];
  6. int ans;
  7. void query(int at, int L, int R, int l, int r){
  8.  
  9.     if( L>=l && R<=r ){
  10.         //cout<<L<<" "<<R<<"\n";
  11.         ans+=carry[at][0];
  12.         return;
  13.     }
  14.  
  15.     if(L==R)return;
  16.     int mid = (L+R)/2;
  17.     query(at*2,L,mid,l,r);
  18.     query(at*2+1,mid+1,R,l,r);
  19. }
  20.  
  21. void update(int at, int L, int R, int l, int r,int inc ){
  22.  
  23.     if(L>r || R<l)return ;
  24.     if(l<=L && r>=R){
  25.  
  26.         int t0 = carry[at][0];
  27.         int t1 = carry[at][1];
  28.         int t2 = carry[at][2];
  29.  
  30.         carry[at][0]=t2;
  31.         carry[at][1]=t0;
  32.         carry[at][2]=t1;
  33.         lazy[at]+=inc;
  34.         return ;
  35.     }
  36.     if(L==R)return;
  37.     int mid = (L+R)/2;
  38.  
  39.     update(at*2,L,mid,l,r);
  40.     update(at*2+1,mid+1,R,l,r);
  41.     carry[at][0]=carry[at*2][0]+carry[at*2+1][0];
  42.     carry[at][1]=carry[at*2][1]+carry[at*2+1][1];
  43.     carry[at][2]=carry[at*2][2]+carry[at*2+1][2];
  44. }
  45.  
  46. void build(int at , int L, int R){
  47.  
  48.     if(L==R){
  49.         carry[at][0]=1;
  50.         return;
  51.     }
  52.     int mid = (L+R)/2;
  53.     build(at*2,L,mid);
  54.     build(at*2+1,mid+1,R);
  55.     carry[at][0]=carry[at*2][0]+carry[at*2+1][0];
  56.     carry[at][1]=carry[at*2][1]+carry[at*2+1][1];
  57.     carry[at][2]=carry[at*2][2]+carry[at*2+1][2];
  58. }
  59.  
  60.  
  61. int main(){
  62.  
  63.     ios::sync_with_stdio(false);
  64.     cin.tie(0);
  65.     int t;
  66.     cin>>t;
  67.     //getchar();
  68.     for(int tt=0;tt<t;tt++){
  69.  
  70.         int n;
  71.         cin>>n;
  72.  
  73.  
  74.         cout<<"Case "<<tt+1<<":\n";
  75.         build(1,1,n);
  76.         int q;
  77.         cin>>q;
  78.         for(int i=0;i<q;i++){
  79.             int type,I,J;
  80.             cin>>type>>I>>J;
  81.             if(type==0)update(1,1,n,I+1,J+1);
  82.             else {
  83.                 ans = 0;
  84.                 query(1,1,n,I+1,J+1);
  85.                 cout<<ans<<"\n";
  86.             }
  87.         }
  88.  
  89.     }
  90. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top