Saleh127

Light Oj 1112

Jun 11th, 2021
209
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. ll a[100005];
  6. ll tree[400005];
  7.  
  8. void treeconstruct(ll node,ll b,ll e)
  9. {
  10.  
  11. if(b==e)
  12. {
  13. tree[node]=a[b];
  14. return;
  15. }
  16.  
  17. ll left = node*2;
  18. ll right = node*2 + 1ll;
  19.  
  20. ll mid=(b+e)/2;
  21.  
  22. treeconstruct(left,b,mid);
  23. treeconstruct(right,mid+1,e);
  24.  
  25. tree[node]=tree[left]+tree[right];
  26.  
  27. }
  28.  
  29. ll queries(ll node,ll b,ll e,ll i,ll j)
  30. {
  31. if(i>e || j<b) return 0;
  32.  
  33. if(b>=i && e<=j) return tree[node];
  34.  
  35.  
  36. ll left = node*2;
  37. ll right = node*2 + 1ll;
  38.  
  39. ll mid=(b+e)/2;
  40.  
  41. ll x=queries(left,b,mid,i,j);
  42.  
  43. ll y=queries(right,mid+1,e,i,j);
  44.  
  45. return x+y;
  46.  
  47. }
  48.  
  49. void update(ll node,ll b,ll e,ll i,ll newv,ll con)
  50. {
  51. if(i>e || i<b) return;
  52.  
  53. if(b>=i && e<=i)
  54. {
  55. if(con==1) tree[node]=newv;
  56. else tree[node]+=newv;
  57. return;
  58. }
  59.  
  60. ll left = node*2;
  61. ll right = node*2 + 1ll;
  62.  
  63. ll mid=(b+e)/2;
  64.  
  65. update(left,b,mid,i,newv,con);
  66.  
  67. update(right,mid+1,e,i,newv,con);
  68.  
  69. tree[node]=tree[left]+tree[right];
  70.  
  71. }
  72.  
  73. int main()
  74. {
  75. ios_base::sync_with_stdio(0);
  76. cin.tie(0);
  77. cout.tie(0);
  78.  
  79. test
  80. {
  81. ll q,n,m,i,j,k,l;
  82.  
  83. cin>>n>>q;
  84.  
  85. for(i=1; i<=n; i++) cin>>a[i];
  86.  
  87. cout<<"Case "<<cs<<":"<<endl;
  88.  
  89. treeconstruct(1ll,1ll,n);
  90.  
  91. while(q--)
  92. {
  93. cin>>k;
  94.  
  95. if(k==1)
  96. {
  97. cin>>l;
  98. l++;
  99.  
  100. m=queries(1ll,1ll,n,l,l);
  101. cout<<m<<endl;
  102.  
  103. update(1ll,1ll,n,l,0ll,1ll);
  104. }
  105. else if(k==2)
  106. {
  107. cin>>j>>l;
  108. j++;
  109. update(1ll,1ll,n,j,l,2ll);
  110. }
  111. else if(k==3)
  112. {
  113. cin>>k>>l;
  114. k++,l++;
  115.  
  116. m=queries(1ll,1ll,n,k,l);
  117. cout<<m<<endl;
  118. }
  119.  
  120. }
  121.  
  122. }
  123.  
  124. return 0;
  125. }
  126.  
Advertisement
Add Comment
Please, Sign In to add comment