spoj1716 Can you answer these queries III

传送门

（分析见正睿2018.10.1笔记）

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

struct node {

      int pre,sur,ans,sum;

};

node d[];

inline node work(node x,node y){

      node res;

      res.sum=x.sum+y.sum;

      res.pre=max(x.pre,x.sum+y.pre);

      res.sur=max(y.sur,y.sum+x.sur);

      res.ans=max(max(x.ans,y.ans),x.sur+y.pre);

      return res;

}

inline void update(int le,int ri,int wh,int pl,int k){

      if(le==ri){

          d[wh].pre=d[wh].sur=d[wh].ans=d[wh].sum=k;

          return;

      }

      int mid=(le+ri)>>;

      if(mid>=pl)update(le,mid,wh<<,pl,k);

        else update(mid+,ri,wh<<|,pl,k);

      d[wh]=work(d[wh<<],d[wh<<|]);

      return;

}

inline node q(int le,int ri,int wh,int x,int y){

      if(le>=x&&ri<=y){

          return d[wh];

      }

      int mid=(le+ri)>>,cnt=;

      node a,b;

      if(mid>=x)cnt+=,a=q(le,mid,wh<<,x,y);

      if(mid<y)cnt+=,b=q(mid+,ri,wh<<|,x,y);

      if(cnt==)return a;

      if(cnt==)return b;

      return work(a,b);

}

int main(){

      int n,m,i,j,k,x,y;

      scanf("%d",&n);

      for(i=;i<=n;i++){

          scanf("%d",&x);

          update(,n,,i,x);

      }

      scanf("%d",&m);

      for(i=;i<=m;i++){

          scanf("%d%d%d",&k,&x,&y);

          if(k==){

            update(,n,,x,y);

          }else {

            printf("%d\n",q(,n,,x,y).ans);

          }

      }

      return ;

}