AcWing 245. 你能回答这些问题吗(线段树)

﹏ヽ暗。殇╰゛Y 2021-11-08 23:40 326阅读 0赞

题目链接：[https://www.acwing.com/problem/content/246/][https_www.acwing.com_problem_content_246]  
给定长度为N的数列A，以及M条指令，每条指令可能是以下两种之一：

1、“1 x y”，查询区间 \[x,y\] 中的最大连续子段和，即 maxx≤l≤r≤y  
\{∑ri=lA\[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≤100000

输入样例：

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

输出样例：

2  
\-1

分析：  
线段树的题目真的恶心。整个人都不好了。  
线段树的题目一般代码量都比较多。对编程水平要求较高。一旦出现问题，对我而言很难找bug。  
线段树支持的操作也是对序列的查询和修改。一般树状数组的题目都可以用线段树来做。  
一个题，如果涉及到区间的操作，一定要看题目信息能否容易的按照区间进行划分与合并（即：需要满足区间可加性）。通俗的讲就是（l~r）的信息能由（l ~ mid）和  
（mid + 1，r）的信息推出来。

看这个题，两个操作：  
1是查询区间（x，y）中的最大连续子段和。  
2是把a\[x\]改成y。  
对于第2个操作，很简单用线段树的单点修改能达到目的。  
对于第1个操作，这就需要仔细考虑了。  
一个结点中的值应该要有哪些属性:  
区间和：sum  
区间最大连续子段和ans  
紧靠左端的最大连续和 lmax  
紧靠右端的最大连续和 rmax  
那么父结点由两个孩子结点推过来的式子为：  
![在这里插入图片描述][20190806210344576.png]  
这个自己理解一下应该是没问题的。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef struct Node
    {
        int l,r,sum,ans;
        int lmax,rmax;
    }Node;
    
    int N,M,a[500100];
    Node node[4 * 500000];
    
    void Build_Tree(int id,int l,int r)
    {
        node[id].l = l; node[id].r = r;
        if(l == r)
        {
            node[id].sum = node[id].ans = node[id].lmax = node[id].rmax = a[l];
            return ;
        }
        int mid = (l + r) >> 1;
        Build_Tree(id << 1,l,mid);
        Build_Tree(id << 1 | 1,mid + 1,r);
        node[id].ans = max(max(node[id << 1].ans,node[id << 1 | 1].ans),node[id << 1].rmax + node[id << 1 | 1].lmax);
        node[id].lmax = max(node[id << 1].lmax,node[id << 1].sum + node[id << 1 | 1].lmax);
        node[id].rmax = max(node[id << 1 | 1].rmax,node[id << 1 | 1].sum + node[id << 1].rmax);
        node[id].sum = node[id << 1].sum + node[id << 1 | 1].sum;
    }
    void Update(int id,int x,int y)
    {
        int l = node[id].l,r = node[id].r;
        if(l == r)
        {
            node[id].ans = y;
            node[id].lmax = node[id].rmax = node[id].sum = y;
            return ;
        }
        int mid = (l + r) >> 1;
        if(x <= mid)
        {
            Update(id << 1,x,y);
        }
        else
            Update(id << 1 | 1,x,y);
        node[id].ans = max(max(node[id << 1].ans,node[id << 1 | 1].ans),node[id << 1].rmax + node[id << 1 | 1].lmax);
        node[id].lmax = max(node[id << 1].lmax,node[id << 1].sum + node[id << 1 | 1].lmax);
        node[id].rmax = max(node[id << 1 | 1].rmax,node[id << 1 | 1].sum + node[id << 1].rmax);
        node[id].sum = node[id << 1].sum + node[id << 1 | 1].sum;
    }
    
    Node Query(int id,int left,int right)
    {
        int l = node[id].l,r = node[id].r;
        if(left <= l && right >= r)
            return node[id];
        int mid = (l + r) >> 1;
        Node A,B,C; int val = -(1 << 30);
        A.ans = A.lmax = A.rmax = A.sum = val;
        B = A;
        C.sum = 0;
        if(left <= mid)
        {
            A = Query(id << 1,left,right);
            C.sum += A.sum;
        }
        if(right > mid)
            {
                B = Query(id << 1 | 1,left,right);
                C.sum += B.sum;
            }
        C.ans = max(max(A.ans,B.ans),A.rmax + B.lmax);
        C.lmax = max(A.lmax,A.sum + B.lmax);
        if(left > mid)
            C.lmax = B.lmax;
        C.rmax = max(B.rmax,B.sum + A.rmax);
        if(right <= mid)
            C.rmax = A.rmax;
        return C;
    }
    
    int main()
    {
        scanf("%d%d",&N,&M);
    
        for(int i = 1; i <= N; i ++)
            {
                scanf("%d",&a[i]);
            }
        Build_Tree(1,1,N);
        while(M --)
        {
            int k,x,y;
            scanf("%d%d%d",&k,&x,&y);
            if(k == 1)
            {
                if(x > y) swap(x,y);
                Node T = Query(1,x,y);
                printf("%d\n",T.ans);
            }
            else
            {
                Update(1,x,y);
            }
        }
    }

[https_www.acwing.com_problem_content_246]: https://www.acwing.com/problem/content/246/
[20190806210344576.png]: /images/20211108/77e9e6c2ae134aa0b74dec961029c0dd.png