题解 P4513 【小白逛公园】

P4513 题解

这还是我第一次给紫题写题解。。。


题目大意:

给定$n$个公园的美观值(可能有负数),求出美观值和最大的连续花园区间 $[l,r]$

实际上就是求区间最大子段和。。。


思路:

这是一道典型的区间统计问题,对于区间统计问题,我们一般使用线段树解决

线段树教程

为了求出区间最大子段和,对于每个区间x,我们需要计算以下四个值:

1
2
3
4
sum[x] : x所代表区间的区间和
ldat[x] : 紧靠区间左端的最大子段和
rdat[x] : 紧靠区间右端的最大子段和
dat[x] : 区间最大子段和

这些值如何求出呢?

首先,我们考虑$dat$:

无标题2.png

对于一个区间的$dat$,它只能由三个途径得来:

  1. 完全在左子区间,即左子区间的$dat$(绿色部分)
  2. 完全在右子区间,即右子区间的$dat$(红色部分)
  3. 跨越中点,即左子区间的$rsum$加上右子区间的$lsum$(黄色部分)

那么,如何求出$ldat$和$rdat$呢?

由于$ldat$和$rdat$的求法相似,只是方向不同,这里只考虑$ldat$的求法 $\dots$

无标题3.png

$ldat$更加简单,只有两种情况:

  1. 完全在左子区间,即左子区间的$ldat$(绿色部分)
  2. 跨越中点,即左子区间的$sum +$ 右子区间的 $ldat$(红色部分)

看到这里,相信大家都已经知道$rdat$怎么求了,这里就不在赘述。。。

至此,问题得到完美解决 $\dots$

怎么可能


Tips:

  1. 测试数据可能会出现$a>b$的情况,需要进行交换…(血的教训)
  2. 查询时要同时返回4个数据并按要求归并…

代码:

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=500001;
int n,m;
struct segment_tree{
int l,r;
int sum,lsum,rsum,dat;
};
segment_tree tree[maxn*4];
//宏定义
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define lsum(x) tree[x].lsum
#define rsum(x) tree[x].rsum
#define dat(x) tree[x].dat
int read()//快读
{
int s=0,w=1;
char c=getchar();
while(c<'0' || c>'9')
{
if(c=='-') w=-1;
c=getchar();
}
while(c>='0' && c<='9')
{
s=(s<<3)+(s<<1)+(c^48);
c=getchar();
}
return s*w;
}
void update(int p)//归并信息
{
sum(p)=sum(p<<1)+sum(p<<1|1); //区间和
lsum(p)=max(lsum(p<<1),sum(p<<1)+lsum(p<<1|1)); //紧靠区间左端的最大子段和
rsum(p)=max(rsum(p<<1|1),sum(p<<1|1)+rsum(p<<1));//紧靠区间右端的最大子段和
dat(p)=max({dat(p<<1),dat(p<<1|1),rsum(p<<1)+lsum(p<<1|1)}); //区间最大子段和
}
void build(int p,int l,int r) //建树
{
l(p)=l,r(p)=r;
if(l(p)==r(p)){ //如果是叶子结点
sum(p)=lsum(p)=rsum(p)=dat(p)=read(); //初始化的同时读入,高效建树
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
update(p);
}
void change(int p,int addr,int c) //单点修改
{
if(l(p)==r(p))
{
sum(p)=lsum(p)=rsum(p)=dat(p)=c;
return;
}
int mid=(l(p)+r(p))>>1;
if(addr<=mid) change(p<<1,addr,c);
else if(addr>mid) change(p<<1|1,addr,c);
update(p);
}
segment_tree ask(int p,int l,int r) //区间查询(要同时返回4个数据)
{
if(l<=l(p) && r>=r(p)) return tree[p];
int ans=0xc0c0c0c0;
int mid=(l(p)+r(p))>>1;
if(r<=mid) return ask(p<<1,l,r);
if(l>mid) return ask(p<<1|1,l,r);
else{
segment_tree x,y,ans;
x=ask(p<<1,l,r),y=ask(p<<1|1,l,r);
ans.sum=x.sum+y.sum;
ans.lsum=max(x.lsum,x.sum+y.lsum);
ans.rsum=max(y.rsum,y.sum+x.rsum);
ans.dat=max({x.dat,y.dat,x.rsum+y.lsum});
return ans;
}
// return ans;
}
int k,a,b;
int main()
{
n=read(),m=read();
build(1,1,n);
for(int i=1;i<=m;i++)
{
k=read();
if(k==1)
{
a=read(),b=read();
if(a>b) swap(a,b);
printf("%d\n",ask(1,a,b).dat);
}
else if(k==2)
{
a=read(),b=read();
change(1,a,b);
}
}
return 0;
}
文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/题解-P4513-【小白逛公园】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏