fork download
copy 
  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
comments (?)
stdin
copy 
8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4
stdout
copy 
5
2
0
https://ideone.com/02fewx
language:
C++14 (gcc 8.3)
created:
67 days 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!