Guest User

Untitled

a guest
Dec 12th, 2019
80
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