CDOJ1598-线段树合并（2017 UESTC Training for Data Structures G）

港控/mmm° 2022-06-13 08:24 104阅读 0赞

**传送门：[CDOJ1598][]**

**题目大意：**

给你n个数m次操作，有两种操作

1，询问区间\[a,b\]的 最大连续子区间

2，将第pos个数变为X

**题目思路：**

线段树区间和并，对于这题我们需维护个区间和和区间最大连续和向左向右最大连续和

对于向上更新时，父区间向左向右连续和为为子区间向左向右连续和和向左向右和加上

相反区间向左向右连续和，这个就和求最大字段和一样，最大连续和左右子区间最大连续和

和中间连续和的最大值，查询这里我们用普通的方法是不行的，因为我们这里不好维左右连续

和的长度，所以查询时可能会越界，所以我们要在要查的区间里不断向右合并更新，最后就是这个

询问区间的最值，我们这里可以用个全局变量来更新查询

**AC代码：**

#include<bits/stdc++.h>
    using namespace std;
    #define lson l,mid,rt<<1
    #define rson mid+1,r,rt<<1|1
    const int maxn = 1e6;
    struct st
    {
        int sum,summax,lsum,rsum;
    }Tree[maxn<<1];
    void pushup(int rt)
    {
        Tree[rt].lsum = max(Tree[rt<<1].lsum,Tree[rt<<1].sum+Tree[rt<<1|1].lsum);
        Tree[rt].rsum = max(Tree[rt<<1|1].rsum,Tree[rt<<1|1].sum+Tree[rt<<1].rsum);
        Tree[rt].sum = Tree[rt<<1].sum+Tree[rt<<1|1].sum;
        Tree[rt].summax = max(max(Tree[rt<<1].summax,Tree[rt<<1|1].summax),Tree[rt<<1].rsum+Tree[rt<<1|1].lsum);
    }
    
    void build(int l,int r,int rt)
    {
    
        if(l==r)
        {
            int x;scanf("%d",&x);
            Tree[rt].lsum=Tree[rt].rsum= Tree[rt].sum = Tree[rt].summax = x;
            return ;
        }
        int mid = (l+r)>>1;
        build(lson);
        build(rson);
        pushup(rt);
    }
    
    int lsum,rsum,sum,summax;
    
    void quary(int L,int R,int l,int r,int rt)
    {
        if(L<=l&&r<=R)
        {
            //在查找区间内不断更新，从左到右（性质）
            
            if(summax == 1e9)
            {
                summax = Tree[rt].summax;
                lsum = Tree[rt].lsum;
                rsum = Tree[rt].rsum;
                sum = Tree[rt].sum;
                return ;
            }
    
            summax = max(max(summax,Tree[rt].summax),rsum+Tree[rt].lsum);
            lsum = max(lsum,sum+Tree[rt].lsum);
            rsum = max(Tree[rt].rsum,Tree[rt].sum+rsum);
            sum = sum+Tree[rt].sum;
    
            return ;
        }
        int mid = (l+r)>>1;
        if(L<=mid)quary(L,R,lson);
        if(R>mid)quary(L,R,rson);
    }
    
    void updata(int l,int r,int rt,int pos,int v)
    {
        if(l==r)
        {
            Tree[rt].lsum =v;
            Tree[rt].rsum=v;
            Tree[rt].sum=v;
            Tree[rt].summax=v;
            return ;
        }
        int mid = (l+r)>>1;
        if(pos<=mid)
        {
            updata(lson,pos,v);
        }
        else updata(rson,pos,v);
        pushup(rt);
    }
    
    int main()
    {
        int n,m;
        scanf("%d%d",&n,&m);
        build(1,n,1);
        while(m--)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(a==1)
            {
                lsum = rsum = sum = summax = 1e9;
                quary(b,c,1,n,1);
                printf("%d\n",summax);
            }
            else
            {
                updata(1,n,1,b,c);
            }
        }
        return 0;
    }

max\{ Ap\+Ap\+1\+…\+Aq

[CDOJ1598]: http://acm.uestc.edu.cn/#/problem/show/1598