ACwing 你能回答这些问题吗(线段树求最大连续字段和）-白红宇

ACwing 你能回答这些问题吗(线段树求最大连续字段和）

阅读量：5012 次

发布时间：2019-06-12

本文共 2341 字，大约阅读时间需要 7 分钟。

给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“1 x y”，查询区间 [x,y] 中的最大连续子段和，即

2、“2 x y”，把 A[x] 改成 y。

对于每个查询指令，输出一个整数表示答案。

输入格式

第一行两个整数N,M。

第二行N个整数A[i]。

接下来M行每行3个整数k,x,y，k=1表示查询（此时如果x>y，请交换x,y），k=2表示修改。

输出格式

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

数据范围

输入样例：

5 31 2 -3 4 51 2 32 2 -11 3 2

输出样例：

2-1

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               const int maxn=5e5+5;typedef long long ll;using namespace std;struct node{ int l,r; ll sum,suml,sumr,summax;}tree[maxn<<2];void pushup(int m){ tree[m].sum=(tree[m<<1].sum+tree[m<<1|1].sum); tree[m].summax=max(max(tree[m<<1].summax,tree[m<<1|1].summax),tree[m<<1].sumr+tree[m<<1|1].suml); tree[m].suml=max(tree[m<<1].suml,tree[m<<1].sum+tree[m<<1|1].suml); tree[m].sumr=max(tree[m<<1|1].sumr,tree[m<<1].sumr+tree[m<<1|1].sum);}void build(int m,int l,int r){ tree[m].l=l; tree[m].r=r; if(l==r) { scanf("%lld",&tree[m].sum); tree[m].summax=tree[m].sum; tree[m].suml=tree[m].sum; tree[m].sumr=tree[m].sum; return ; } int mid=(l+r)>>1; build(m<<1,l,mid); build(m<<1|1,mid+1,r); pushup(m);}void update(int m,int pos,ll val){ if(tree[m].l==tree[m].r&&tree[m].l==pos) { tree[m].sum=val; tree[m].summax=tree[m].sum; tree[m].suml=tree[m].sum; tree[m].sumr=tree[m].sum; return ; } int mid=(tree[m].l+tree[m].r)>>1; if(pos<=mid) { update(m<<1,pos,val); } else { update(m<<1|1,pos,val); } pushup(m);}node query(int m,int l,int r){ if(tree[m].l==l&&tree[m].r==r) { return tree[m]; } int mid=(tree[m].l+tree[m].r)>>1; if(r<=mid) { return query(m<<1,l,r); } else if(l>mid) { return query(m<<1|1,l,r); } else { node treel,treer,temp; treel=query(m<<1,l,mid); treer=query(m<<1|1,mid+1,r); temp.sum=treel.sum+treer.sum; temp.summax=max(max(treel.summax,treer.summax),treel.sumr+treer.suml); temp.suml=max(treel.suml,treel.sum+treer.suml); temp.sumr=max(treer.sumr,treer.sum+treel.sumr); return temp; }}int main(){ int n,q; cin>>n>>q; build(1,1,n); int op,l,r; while(q--) { scanf("%d",&op); if(op==1) { scanf("%d%d",&l,&r); if(l>r) { swap(l,r); } printf("%lld\n",query(1,l,r).summax); } else { scanf("%d%d",&l,&r); update(1,l,r); } } return 0;}