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

深碍√TFBOYSˉ_ 2021-10-29 15:24 271阅读 0赞

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

1、“1 x y”，查询区间 \[x,y\] 中的最大连续子段和，即 maxx≤l≤r≤ymaxx≤l≤r≤y\{ ∑ri=lA\[i\]∑i=lrA\[i\]\}。

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表示修改。

#### 输出格式 ####

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

每个答案占一行。

#### 数据范围 ####

N≤500000,M≤100000N≤500000,M≤100000

#### 输入样例： ####

5 3
    1 2 -3 4 5
    1 2 3
    2 2 -1
    1 3 2

#### 输出样例： ####

2
    -1

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<queue>
    #include<stack>
    #include<set>
    #include<map>
    #include<vector>
    #include<cmath>
    
    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;
    }

转载于:https://www.cnblogs.com/Staceyacm/p/11319463.html