首页 > itarticle > 【luogu p4513】小白逛公园

【luogu p4513】小白逛公园

admin 11月 11, 2020 0

线段树题，略微还用到了一些分治思想来求最大子段和。

原题

题意简述：维护一个有$n$个元素的序列，支持单点修改和查询区间最大子段和。其中$n<=500000$，操作数$m<=100000$。

分析：本题要求维护区间最大子段和。静态的区间最大子段和有两种求法：一是动态规划，二是分治。

如果要用动态规划的话，显然每一次修改之后你都要再跑一遍，这样的复杂度是无法接受的。

考虑分治。设区间中点为$mid$，一个区间的最大子段和无非有三种情况：

  1. 就是mid左边的最大子段和
  2. 就是mid右边的最大子段和
  3. 横跨mid，左边有一部分，右边有一部分

一二两种情况都很简单，那么第三种情况下，容易想到以$mid$为界限，将整个区间分成两部分，那么“横跨$mid$的最大子段和”即为“左区间的右端向左延伸的最大子段和”加上“右区间的左端向右延伸的最大子段和”。
看图说话
(小吐槽：sm.ms怎么挂了，只能先用奇奇怪怪的图床了)

非常明显的二分，线段树使用可能。并且这样的话线段树单个节点存储的信息也就得到了：

1
2
3
4
5
6
7
 
struct node
{
    int lv;//本区间从左端向右延伸的最大子段和
    int rv;//本区间从右端向左延伸的最大子段和
    int tot;//本区间之和
    int l,r,ans;//左边界，右边界，以及本区间的【真.最大子段和】
};

非常明显，对于叶子结点，有tree[p].lv=tree[p].rv=tree[p].tot=tree[p].ans。

因为只要求单点更新，所以这里的更新非常好办。只需要递归到叶子结点，然后一层一层向上传就可以了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
//segtree by 枳椛明驿墙
#include<bits/stdc++.h>
using namespace std;
const int N=500001;
struct node
{
    int lv,rv,tot,l,r,ans;
}tree[N*4];
int n,m;
void read(int &x)
{
    int res=0,f=1;char ch;
    for(;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
    for(;isdigit(ch);ch=getchar()) res=res*10+(ch-'0');
    x=res*f;
}
void pushup(int p)
{
    tree[p].lv=max(tree[p<<1].lv,tree[p<<1].tot+tree[(p<<1)+1].lv);
    tree[p].rv=max(tree[(p<<1)+1].rv,tree[(p<<1)+1].tot+tree[p<<1].rv);
    tree[p].tot=tree[p<<1].tot+tree[(p<<1)+1].tot;
    tree[p].ans=max(tree[p<<1].ans,max(tree[(p<<1)+1].ans,tree[p<<1].rv+tree[(p<<1)+1].lv));
}
void build(int l,int r,int p)
{
    tree[p].l=l;tree[p].r=r;
    if (l==r)
    {
    	int x;read(x);
        tree[p].rv=tree[p].lv=tree[p].tot=tree[p].ans=x;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,p<<1);build(mid+1,r,(p<<1)+1);
    pushup(p);
}
void updata(int x,int y,int p)
{
    if (tree[p].l==tree[p].r)
    {
        tree[p].rv=tree[p].lv=tree[p].tot=tree[p].ans=y;
        return;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if (x<=mid) updata(x,y,p<<1);
    else updata(x,y,(p<<1)+1);
    pushup(p);
}
node query(int x,int y,int p)
{
    if (x<=tree[p].l&&tree[p].r<=y) return tree[p];
    int mid=(tree[p].l+tree[p].r)>>1;
    if (y<=mid) return query(x,y,p<<1);
    else if (x>mid) return query(x,y,(p<<1)+1);
    else
    {
        node t,t1=query(x,mid,(p<<1)),t2=query(mid+1,y,(p<<1)+1);
        t.lv=max(t1.lv,t1.tot+t2.lv);
        t.rv=max(t1.rv+t2.tot,t2.rv);
        t.tot=t1.tot+t2.tot;
        t.ans=max(max(t1.ans,t2.ans),t1.rv+t2.lv);
        return t;
    }
}
int main()
{
    read(n);read(m);
    build(1,n,1);
    for(int i=1;i<=m;i++)
    {
        int k,x,y;
        read(k);read(x);read(y);
        if (k==1)
        {
            if (x>y) swap(x,y);
            printf("%dn",query(x,y,1).ans);
        }
        if (k==2)
        {
            updata(x,y,1);
        }
    }
    return 0;
}

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能