题解 P2096 【最佳旅游线路】
顾z
2018-09-24 20:00:37
# [顾](https://www.luogu.org/blog/RPdreamer/#)[z](https://www.cnblogs.com/-guz/)
~~你没有发现两个字里的blog都不一样嘛~~ qwq
题目描述-->[p2096 最佳旅游路线](https://www.luogu.org/problemnew/show/P2096)
## 分析
自己xjb分析了一通,发现只需要求出每一列的最大值,然后**求整个范围的最大子段和**即可.
一想,woc,最大子段和.线段树啊!.
**线段树维护最大子段和**操作.
考虑到大多数人可能不会,所以我把我博客的一些部分取了过来 qwq.
### 数组定义
$lsum[ ]$代表 该区间左端点开始的最大连续和.
$rsum[ ]$代表 该区间右端点开始的最大连续和.
$ssum[ ]$代表 区间内最大连续和.
$sum[ ]$ 代表区间和.
### Que and Ans
##### Q:已知一个区间的左右区间的最大连续和,如何合并?
##### A:这个区间的最大连续和要么是左子区间的最大连续和,要么是右子区间的最大连续和.
##### 要么是左子区间的最大右起子段和+右子区间的最大左起字段和.
``code``：$ssum[o]=max(max(ssum[lson],ssum[rson]),rsum[lson]+lsum[rson])$
##### Q:如何更新区间最大左起子段和.
##### A:新区间的最大左起子段和.要么是其左子区间最大连续和,要么是其左子区间和+右子区间的左起子段和.
**最大右起子段和同理**
``code``：$lsum[o]=max(lsum[lson],sum[lson]+lsum[rson])$
$rsum[o]=max(rsum[rson],sum[rson]+rsum[lson])$
更新操作类似单点修改
不能理解的话可以画图演示一下.qwq
或者等我在博客上画图 qwq.(具体时间未知.
-------------------代码------------------
```cpp
#include<bits/stdc++.h>
#define IL inline
#define int long long
#define RI register int
#define N 200008
#define ls o<<1
#define rs o<<1|1
using namespace std;
IL void in(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}
while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int tr[N<<2],ssum[N<<2],lsum[N<<2],rsum[N<<2],n,m,a[20001];
IL void up(int o)
{
tr[o]=tr[ls]+tr[rs];
ssum[o]=max(max(ssum[ls],ssum[rs]),rsum[ls]+lsum[rs]);
lsum[o]=max(lsum[ls],tr[ls]+lsum[rs]);
rsum[o]=max(rsum[rs],tr[rs]+rsum[ls]);
}
IL void build(int o,int l,int r)
{
if(l==r)
{
tr[o]=a[l];
ssum[o]=lsum[o]=rsum[o]=tr[o];
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
up(o);
}
IL int query(int o,int l,int r,int x,int y)
{
if(l<=x and y>=r)return ssum[o];
int mid=(l+r)>>1;
int ret=-2147483647;
if(x<=mid)ret=max(query(ls,l,mid,x,y),ret);
if(y>mid)ret=max(query(rs,mid+1,r,x,y),ret);
return ret;
}
main(void )
{
in(n),in(m);
for(RI i=1;i<=m;i++)a[i]=-2147483647;
for(RI i=1;i<=n;i++)
for(RI j=1,x;j<=m;j++)
{
in(x);
a[j]=max(a[j],x);
}
build(1,1,m);
printf("%lld",query(1,1,m,1,m));
}
```