fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mx 100009
  4. #define ll long long int
  5. ll arr[mx];
  6. //ll tree[mx*4];
  7. //ll state=0;
  8. struct nd{
  9.     ll high;
  10.     ll sum;
  11. };
  12. nd tree[mx*4];
  13. ll ans=-1;
  14. ll res;
  15. void init(ll node,ll l,ll r){
  16.     if(l==r){
  17.         tree[node].high=arr[l]; //cout<<"lf node:"<<node<<" val:"<<tree[node].high<<endl;
  18.         tree[node].sum=arr[l];
  19.         return;
  20.     }
  21.     ll Left=node*2;
  22.     ll Right=node*2+1;
  23.     ll mid=(l+r)/2;
  24.     init(Left,l,mid);
  25.     init(Right,mid+1,r);
  26.     tree[node].high=max(tree[Left].high,tree[Right].high);
  27.     ll hh=-1;
  28.     hh=max(hh,tree[Left].high+tree[Right].high);
  29.     hh=max(hh,tree[Left].sum);
  30.     hh=max(hh,tree[Right].sum);
  31.     tree[node].sum=hh; //cout<<"node:"<<node<<" val:"<<tree[node].sum<<" high:"<<tree[node].high<<endl;
  32. }
  33.  
  34. ll query(ll node,ll l,ll r,ll i,ll j){
  35.     if(l>j || r<i){
  36.         return 0;
  37.     }
  38.     if(l>=i && r<=j){//cout<<"node:"<<node<<" val:"<<tree[node].sum<<endl;  cout<<"l:"<<l<<" r:"<<r<<endl;
  39.         if(tree[node].sum>res){
  40.             res=tree[node].sum;
  41.         }
  42.         return tree[node].high;
  43.     }
  44.     ll Left=node*2;
  45.     ll Right=node*2+1;
  46.     ll mid=(l+r)/2;
  47.     ll p1=query(Left,l,mid,i,j);
  48.     ll p2=query(Right,mid+1,r,i,j);
  49.     if(p1+p2>res){ //cout<<p1<<"+"<<p2<<endl;
  50.         res=p1+p2;
  51.     }
  52.     return max(p1,p2);
  53. }
  54.  
  55. void update(ll node,ll l,ll r,ll pos,ll val){
  56.     if(l>pos || r<pos){
  57.         return;
  58.     }
  59.     if(l==r){
  60.         tree[node].high=val;
  61.         tree[node].sum=val;
  62.         return;
  63.     }
  64.     ll Left=node*2;
  65.     ll Right=node*2+1;
  66.     ll mid=(l+r)/2;
  67.     update(Left,l,mid,pos,val);
  68.     update(Right,mid+1,r,pos,val);
  69.     tree[node].high=max(tree[Left].high,tree[Right].high);
  70.     tree[node].sum=max(tree[node].sum,tree[Left].high+tree[Right].high);
  71. }
  72.  
  73. int main(){
  74.     ll n,i,j;
  75.     while(scanf("%lld",&n)==1){
  76.         for(i=1;i<=n;i++){
  77.             scanf("%lld",&arr[i]);
  78.         }
  79.         init(1,1,n);
  80.         char ch;
  81.         ll q;
  82.         scanf("%lld",&q);
  83.         getchar();
  84.         for(i=1;i<=q;i++){
  85.             scanf("%c",&ch);
  86.             if(ch=='Q'){
  87.                 ll x,y; //cout<<"Q pressed"<<endl;
  88.                 scanf("%lld %lld",&x,&y);
  89.                 query(1,1,n,x,y);
  90.                 printf("%lld\n",res);
  91.                 res=-1;
  92.                 //state=0;
  93.             }
  94.             else{
  95.                 ll x,y;
  96.                 scanf("%lld %lld",&x,&y);
  97.                 update(1,1,n,x,y);
  98.             }
  99.             getchar();
  100.         }
  101.     }
  102.     return 0;
  103. }
Success #stdin #stdout 0s 10136KB
comments (?)
stdin
copy 
2
1 2
2
U 1 0
Q 1 2
stdout
copy 
3
https://ideone.com/liPU8O
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

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!