【线段树】【cogs775】山海经 775.山海经

74 阅读 0 评论 49 点赞

我是靠谱客的博主兴奋抽屉，最近开发中收集的这篇文章主要介绍【线段树】【cogs775】山海经 775.山海经，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

775.山海经

★★★ 输入文件： hill.in 输出文件： hill.out 简单对比

时间限制：1 s 内存限制：128 MB

【问题描述】

“南山之首日鹊山。其首日招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名日祝余，食之不饥……又东三百里，日堂庭之山，多棪木，多白猿，多水玉，多黄金。

又东三百八十里，日猨翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。……”

《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。某天，你的地理老师想重游《山海经》中的路线，为了简化问题，老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第a座山到第b座山的中间某段路 (i,j) ( i , j ) 。能使他感到最满意，即 (i,j) ( i , j ) 这条路上所有山的喜恶度之和是 (c,d) ( c , d ) (a≤c≤d≤b) ( a ≤ c ≤ d ≤ b ) 最大值。于是老师便向你请教，你能帮助他吗?值得注意的是，在《山海经》中，第 i i 座山只能到达第 i+1 i + 1 座山。

【输入】

输入第1行是两个数， n n ， $m$ ， 2≤n≤100000 2 ≤ n ≤ 100000 ， 1≤m≤100000 1 ≤ m ≤ 100000 ， n n 表示一共有 $n$ 座山， m m 表示老师想查询的数目。

第2行是 $n$ 个整数，代表 n n 座山的喜恶度，绝对值均小于 $10000$ 。

以下 m m 行每行有 $a$ ， b b 两个数， $1 \leq a \leq j \leq b \leq m$ ，表示第 a a 座山到第 $b$ 座山。

【输出】

一共有 m m 行，每行有3个数 $i$ ， j j ， $s$ ，表示从第 i i 座山到第 $j$ 座山总的喜恶度为 s s 。显然，对于每个查询，有 $a \leq i \leq j \leq b$ ，如果有多组解，则输出 i i 最小的，如果 $i$ 也相等，则输出 j j 最小的解。

【输入样例】

5 3
5 -6 3 -1 4
1 3
1 5
5 5

【输出样例】

1 1 5
3 5 6
5 5 4

【题解】

题目大意：给定 $n$ 个数，求 [L,R] [ L , R ] 区间的最大连续子序列的左端点，右端点以及它的和。

首先考虑DP，DP可以快速求 [1,R] [ 1 , R ] 区间的最大连续子序列，但对于 [L,R] [ L , R ] 区间的情况就束手无策了。

想到区间问题有很多用线段树求，那么我们就可以用线段树来做这道题。

令 f(L,R) f ( L , R ) 为 [L,R] [ L , R ] 区间的最大连续子序列的和，那么 f(L,R)=max{f(L,mid),f(mid+1,R)} f ( L , R ) = m a x { f ( L , m i d ) , f ( m i d + 1 , R ) } 。

码一遍代码，发现连样例都过不去，仔细想，如果 f(L,R)=f(i,j) f ( L , R ) = f ( i , j ) 且 i<mid,j>mid i < m i d , j > m i d ，那么这样没有算到。

那我们再定义 SumL(L,R),SumR(L,R) S u m L ( L , R ) , S u m R ( L , R ) ，分别为从 R R 往前推的最大连续子序列的和，从 $l$ 往后推的最大连续子序列的和，因为线段树的性质，可得这段子序列的左端点 ≥L ≥ L ，右端点 ≤R ≤ R ，那么 f(L,R)=max{SumL(L,mid)+SumR(mid+1,R)},mid=L+R2 f ( L , R ) = m a x { S u m L ( L , m i d ) + S u m R ( m i d + 1 , R ) } , m i d = L + R 2

这样就把所有情况考虑到了。

对于维护 SumL(L,R) S u m L ( L , R ) ，
易得 SumL(L,R)=max{SumL(L,mid),Sum(L,mid)+SumL(mid+1,R)}，mid=L+R2 S u m L ( L , R ) = m a x { S u m L ( L , m i d ) , S u m ( L , m i d ) + S u m L ( m i d + 1 , R ) } ， m i d = L + R 2
其中 Sum(L,R) S u m ( L , R ) 是 L L 到 $r$ 的子序列和。

SumR(L,R) S u m R ( L , R ) 同理。

又因为需要知道左右端点，再开4个量维护 SumL(L,R) S u m L ( L , R ) 这段子序列的左端点， SumR(L,R) S u m R ( L , R ) 这段子序列的右端点，以及 f(L,R) f ( L , R ) 的左右端点即可。

那么这道题就完美解决了。

#include<cstdio>
#include<algorithm>
using namespace std;
struct ad{
//L,R表示这个节点覆盖的线段的左端点和右端点，但因为是线段树，可以快速得出L和R的值，在此就不定义了 
int LSum,RL; //LSum表示从L往后，最大的连续喜恶值之和，RL表示LSum这段连续子序列的右端点 
int RSum,LR; //RSum表示从R往前，最大的连续喜恶值之和，LR表示RSum这段连续子序列的左端点
int Sum; //Sum为L到R的数字之和 
int Max,LMax,RMax; //Max表示L到R中最大的连续喜恶值之和，LMax表示这段连续子序列的左端点，RMax表示这段连续子序列的右端点 
inline void newnode(int data,int id){LSum=RSum=Sum=Max=data;RL=LR=LMax=RMax=id;}
//给节点赋初值，因为只有l==R时需要赋初值，所以LSum,RSum,Sum,Max都等于A[L]，RL,LR,LMax,RMax都等于L 
}T[400005];
int N,M,A[100005];
inline int read(){
int Res=0,f=1;char ch=getchar();
while (ch>'9'||ch<'0') f=(ch=='-')?-f:f,ch=getchar();
while (ch>='0'&&ch<='9') Res=Res*10+ch-'0',ch=getchar();
return Res*f;
}
inline void updata(ad &P,ad A,ad B){ //更新 
P.LSum=A.LSum;P.RL=A.RL;
P.RSum=B.RSum;P.LR=B.LR;
P.Sum=A.Sum+B.Sum;
P.Max=A.Max;P.LMax=A.LMax;P.RMax=A.RMax;
if (A.Sum+B.LSum>P.LSum) P.LSum=A.Sum+B.LSum,P.RL=B.RL;
if (B.Sum+A.RSum>P.RSum) P.RSum=B.Sum+A.RSum,P.LR=A.LR;
if (A.RSum+B.LSum>P.Max){//题目要求有多组解输出i最小的，所以先判这一段
P.Max=A.RSum+B.LSum;
P.LMax=A.LR;P.RMax=B.RL;
}
if (B.Max>P.Max){
P.Max=B.Max;
P.LMax=B.LMax;P.RMax=B.RMax;
}
}
inline void build(int p,int L,int R){
if (L==R){T[p].newnode(A[L],L);return ;}
int mid=(R+L)>>1;
if (L<=mid) build(p<<1,L,mid);
if (R>mid) build(p<<1|1,mid+1,R);
updata(T[p],T[p<<1],T[p<<1|1]);
}
inline ad query(int p,int L,int R,int qL,int qR){ //qL,qR表示询问的L,R 
if (qL==L&&qR==R) return T[p];
if (L==R) return T[p];
int mid=(L+R)>>1;
if (mid>=qR) return query(p<<1,L,mid,qL,qR); //如果 [L,mid] 区间包含 [qL,qR] 就直接跑下去 
if (qL>mid) return query(p<<1|1,mid+1,R,qL,qR); //如果 [mid+1,R] 区间包含 [qL,qR] 就直接跑下去 
ad Ans1=query(p<<1,L,mid,qL,mid),Ans2=query(p<<1|1,mid+1,R,mid+1,qR),Ans; //有交错区间就和普通线段树一样，刷最大的 
updata(Ans,Ans1,Ans2);
return Ans;
}
int main()
{
freopen("hill.in","r",stdin);
freopen("hill.out","w",stdout);
N=read();M=read();
for (int i=1;i<=N;i++) A[i]=read();
build(1,1,N);
for (int i=1;i<=M;i++) {
int L=read(),R=read();
ad Res=query(1,1,N,L,R);
printf("%d %d %dn",Res.LMax,Res.RMax,Res.Max);
}
return 0;
}