- #include <bits/stdc++.h>
- using namespace std;
- const int maxn=5e5+10;
- inline int read(){
- int x=0,f=1;char ch;
- do{ch=getchar();if(ch=='-')f=-1;}while(!isdigit(ch));
- do{x=x*10+ch-'0';ch=getchar();}while(isdigit(ch));
- return f*x;
- }
- int n,m,a[maxn];
- struct node{
- #define lson t[k].lc
- #define rson t[k].rc
- int lc,rc;
- int sum,lmax,rmax,dat;
- }t[maxn<<1];
- int tot=1;
- inline void pushup(int k){
- t[k].sum=t[lson].sum+t[rson].sum;
- t[k].lmax=max(t[lson].lmax,t[lson].sum+t[rson].lmax);
- t[k].rmax=max(t[rson].rmax,t[rson].sum+t[lson].rmax);
- t[k].dat=max(max(t[lson].dat,t[rson].dat),t[lson].rmax+t[rson].lmax);
- }
- void build(int k,int l,int r){
- if(l==r){
- t[k].sum=t[k].lmax=t[k].rmax=t[k].dat=a[l];
- return;
- }
- int mid=l+r>>1;
- lson=++tot,build(lson,l,mid);
- rson=++tot,build(rson,mid+1,r);
- pushup(k);
- }
- void modify(int k,int l,int r,int pos,int val){
- if(l==r){
- t[k].sum=t[k].lmax=t[k].rmax=t[k].dat=val;
- return;
- }
- int mid=l+r>>1;
- if(pos<=mid)modify(lson,l,mid,pos,val);
- else modify(rson,mid+1,r,pos,val);
- pushup(k);
- }
- node query(int k,int l,int r,int x,int y){
- if(l==x&&r==y)return t[k];
- int mid=l+r>>1;
- if(y<=mid)return query(lson,l,mid,x,y);
- else if(x>mid)return query(rson,mid+1,r,x,y);
- else{
- node ls=query(lson,l,mid,x,mid);
- node rs=query(rson,mid+1,r,mid+1,y);
- node res;
- res.sum=ls.sum+rs.sum;
- res.lmax=max(ls.lmax,ls.sum+rs.lmax);
- res.rmax=max(rs.rmax,rs.sum+ls.rmax);
- res.dat=max(max(ls.dat,rs.dat),ls.rmax+rs.lmax);
- return res;
- }
- }
- void read_and_parse(){
- n=read(),m=read();
- for(int i=1;i<=n;i++)a[i]=read();
- build(1,1,n);
- }
- void solve(){
- while(m--){
- int k=read(),x=read(),y=read();
- if(k==1){
- if(x>y)swap(x,y);
- printf("%d\n",query(1,1,n,x,y).dat);
- }else modify(1,1,n,x,y);
- }
- }
- int main(){
- read_and_parse();
- solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2803464.html