cogs755 山海经

山海经"/>

cogs755 山海经

775. 山海经

【问题描述】

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

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

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

【输入】

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

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

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

【输出】

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

【输入样例】

5 3

5 -6 3 -1 4

1 3

1 5

5 5

【输出样例】

1 1 5

3 5 6

5 5 4

正解为线段树。题意大概为求区间最长连续和。

首先，考虑结果的来源只有三个地方，区间前缀，区间后缀和区间的中间，所以要维护这三个变量，答案就是三者之一。
定义四个变量sum,lmax,rmax,ma，分别表示区间和，最大前缀和，最大后缀和，最大中间和。为了维护询问的左右边界，定义lpos为区间最大前缀和的右边界,rpos为区间最大后缀和的左边界，ml，mr为中间和的左右边界。那么很容易想到以下合并方法

(z为当前节点，lch,rch分别为左右子节点)

1. tr[z].lmax=max(tr[lch].lmax,tr[lch].sum+tr[rch].lmax);

2. tr[z].rmax=max(tr[rch].rmax,tr[rch].sum+tr[lch].rmax);

3. tr[z].ma=max(tr[lch].ma,tr[rch].ma,tr[lch].rmax+tr[rch].lmax);

在维护值时同时把下标维护(注意大小相同时按题目要求处理，因为这WA了2次)

接下来是查询，我们可以换一下思路，把以往线段树查询的点换为一条线段，那么这条线段就可以用上面的三种方法维护，最终结果就是你查询得到的那条线段的lmax,rmax,ma的最大值。

#include<cstdio>
#define maxn 400005
using namespace std;
int n,m,inf=0xfffffff;
struct tree{int lc,rc,sum,lmax,rmax,ma,lpos,rpos,ml,mr;tree(){lmax=rmax=ma=-inf;sum=0;}}tr[maxn];
void pushup(int x)
{int lch=x<<1,rch=lch|1;tr[x].sum=tr[lch].sum+tr[rch].sum;if(tr[lch].lmax<tr[lch].sum+tr[rch].lmax) tr[x].lmax=tr[lch].sum+tr[rch].lmax,tr[x].lpos=tr[rch].lpos;else tr[x].lmax=tr[lch].lmax,tr[x].lpos=tr[lch].lpos;if(tr[rch].rmax<tr[rch].sum+tr[lch].rmax) tr[x].rmax=tr[rch].sum+tr[lch].rmax,tr[x].rpos=tr[lch].rpos;else tr[x].rmax=tr[rch].rmax,tr[x].rpos=tr[rch].rpos;if(tr[lch].ma<tr[rch].ma){if(tr[rch].ma<=tr[lch].rmax+tr[rch].lmax) tr[x].ma=tr[lch].rmax+tr[rch].lmax,tr[x].ml=tr[lch].rpos,tr[x].mr=tr[rch].lpos;else tr[x].ma=tr[rch].ma,tr[x].ml=tr[rch].ml,tr[x].mr=tr[rch].mr;}else if(tr[lch].ma<tr[lch].rmax+tr[rch].lmax) tr[x].ma=tr[lch].rmax+tr[rch].lmax,tr[x].ml=tr[lch].rpos,tr[x].mr=tr[rch].lpos;else if(tr[lch].ma==tr[lch].rmax+tr[rch].lmax){	 tr[x].ma=tr[lch].ma;if(tr[lch].rpos<tr[lch].ml) tr[x].ml=tr[lch].rpos,tr[x].mr=tr[rch].lpos;else tr[x].ml=tr[lch].ml,tr[x].mr=tr[lch].mr;}else tr[x].ma=tr[lch].ma,tr[x].ml=tr[lch].ml,tr[x].mr=tr[lch].mr;
}
void cmp(tree x,tree y,tree &z)
{z.lc=x.lc;z.rc=y.rc;z.sum=x.sum+y.sum;if(x.lmax<x.sum+y.lmax) z.lmax=x.sum+y.lmax,z.lpos=y.lpos;else z.lmax=x.lmax,z.lpos=x.lpos;if(y.rmax<y.sum+x.rmax) z.rmax=y.sum+x.rmax,z.rpos=x.rpos;else z.rmax=y.rmax,z.rpos=y.rpos;if(x.ma<y.ma){if(y.ma<=x.rmax+y.lmax) z.ma=x.rmax+y.lmax,z.ml=x.rpos,z.mr=y.lpos;else z.ma=y.ma,z.ml=y.ml,z.mr=y.mr;}else if(x.ma<x.rmax+y.lmax) z.ma=x.rmax+y.lmax,z.ml=x.rpos,z.mr=y.lpos;else if(x.ma==x.rmax+y.lmax){	 z.ma=x.ma;if(x.rpos<x.ml) z.ml=x.rpos,z.mr=y.lpos;else z.ml=x.ml,z.mr=x.mr;}else z.ma=x.ma,z.ml=x.ml,z.mr=x.mr;
}
void build(int x,int y,int z)
{tr[z].lc=x;tr[z].rc=y;if(x==y){int tmp;scanf("%d",&tmp);tr[z].sum=tr[z].lmax=tr[z].rmax=tr[z].ma=tmp;tr[z].lpos=tr[z].rpos=tr[z].ml=tr[z].mr=x;return;}int mid=x+y>>1,lch=z<<1,rch=lch|1;build(x,mid,lch);build(mid+1,y,rch);pushup(z);
}
tree query(int x,int y,int z)
{if(tr[z].lc>=x&&tr[z].rc<=y)return tr[z];int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1;tree t1,t2,t3;if(x<=mid) t1=query(x,y,lch);if(mid<y) t2=query(x,y,rch);t1.lc=x;t1.rc=mid;t2.lc=mid+1;t2.rc=y;cmp(t1,t2,t3);return t3;
}
void print(tree x)
{if(x.lmax>=x.rmax){if(x.lmax>=x.ma) printf("%d %d %d\n",x.lc,x.lpos,x.lmax);else printf("%d %d %d\n",x.ml,x.mr,x.ma);}else if(x.rmax>x.ma) printf("%d %d %d\n",x.rpos,x.rc,x.rmax);else printf("%d %d %d\n",x.ml,x.mr,x.ma);
}
int main()
{freopen("hill.in","r",stdin);freopen("hill.out","w",stdout);scanf("%d%d",&n,&m);build(1,n,1);int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);tree tmp=query(x,y,1);print(tmp);}return 0;
}