fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define input(a,start,end) for(int i=start;i<end;i++){cin>>a[i];}
  5. #define output(a,start,end) for(int i=start;i<end;i++){cout<<a[i]<<" ";}
  6.  
  7. int lazy[2000001];
  8. void build(int ind, int low, int high, vector<int>&psum, vector<int>&seg){
  9. if(low==high){
  10. seg[ind] = psum[low];
  11. return;
  12. }
  13. int mid = low+(high-low)/2;
  14. build(2*ind+1, low, mid, psum, seg);
  15. build(2*ind+2, mid+1, high, psum, seg);
  16. seg[ind] = max(seg[2*ind+1], seg[2*ind+2]);
  17. return;
  18. }
  19.  
  20. void lazy_prop(vector<int>&seg,int ind,int low,int high){
  21. seg[ind]+=lazy[ind];
  22. lazy[2*ind+1]+=lazy[ind];
  23. lazy[2*ind+2]+=lazy[ind];
  24. lazy[ind] = 0;
  25. }
  26. int range_query(int ind, int low, int high, int l, int r, vector<int>&seg){
  27. lazy_prop(seg,ind,low,high);
  28. //no overlap
  29. if(high<l || r<low){
  30. return LLONG_MIN;
  31. }
  32. //complete overlap
  33. if(low>=l && high<=r){
  34. return seg[ind];
  35. }
  36. int mid = low+(high-low)/2;
  37. int l_part = range_query(2*ind+1, low, mid, l, r, seg);
  38. int r_part = range_query(2*ind+2, mid+1, high, l, r, seg);
  39. return max(l_part, r_part);
  40. }
  41. void range_update(int l,int r, int u, int ind, int low, int high, vector<int>&seg){
  42. //no overlap
  43. if(high<l || r<low){
  44. return;
  45. }
  46. //complete overlap
  47. if(low>=l && high<=r){
  48. lazy[ind]+=u;
  49. lazy_prop(seg,ind,low,high);
  50. return;
  51. }
  52. int mid = low+(high-low)/2;
  53. range_update(l,r,u,2*ind+1,low,mid,seg);
  54. range_update(l,r,u,2*ind+2,mid+1,high,seg);
  55. seg[ind] = max(seg[2*ind+1], seg[2*ind+2]);
  56. return;
  57. }
  58. int point_query(int ind,int low,int high,int k,vector<int>&seg){
  59. lazy_prop(seg,ind,low,high);
  60. if(low==high) return seg[ind];
  61. int mid = low+(high-low)/2;
  62. if(k<=mid) return point_query(2*ind+1,low,mid,k,seg);
  63. return point_query(2*ind+2,mid+1,high,k,seg);
  64. }
  65. void solve(){
  66. int n,q; cin>>n>>q;
  67. vector<int>a(n);
  68. memset(lazy,0,sizeof(lazy));
  69. input(a,0,n);
  70. vector<int>seg(4*n+1);
  71. vector<int>psum(n);
  72. psum[0] = a[0];
  73. for(int i=1;i<n;i++) psum[i] = psum[i-1]+a[i];
  74. build(0,0,n-1,psum,seg);
  75. for(int i=0;i<q;i++){
  76. int type; cin>>type;
  77. if(type==1){
  78. int k,val; cin>>k>>val;
  79. range_update(k-1,n-1,val-a[k-1],0,0,n-1,seg);
  80. a[k-1] = val;
  81. }
  82. else{
  83. int l,r; cin>>l>>r;
  84. int offset = l>=2?point_query(0,0,n-1,l-2,seg):0;
  85. cout<<max((int)0,range_query(0,0,n-1,l-1,r-1,seg)-offset)<<endl;
  86. }
  87. }
  88.  
  89. }
  90. signed main(){
  91. solve();
  92. cout<<endl;
  93. }
  94. //some thing is wrong in this sol... first two test cases are failing
Success #stdin #stdout 0.01s 19196KB
stdin
8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4
stdout
5
2
0