775. [SOJ 1136] 山海经★★★ 输入文件：hill.in 输出文件：hill.out简单对比时间限制：1 s 内存限制：128 MB
【问题描述】
“南山之首日鹊山。其首日招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名日祝余，食之不饥……又东三百里，日堂庭之山，多棪木，多白猿，多水玉，多黄金。
又东三百八十里，日猨翼之山，其中多怪兽，水多怪鱼，多白玉，多蝮虫，多怪蛇，名怪木，不可以上。……”
《山海经》是以山为纲，以海为线记载古代的河流、植物、动物及矿产等情况，而且每一条记录路线都不会有重复的山出现。某天，你的地理老师海东想重游《山海经》中的路线，为了简化问题，海东老师已经把每座山用一个整数表示他对该山的喜恶程度，他想知道第a座山到第b座山的中间某段路(i,j)。能使他感到最满意，即(i，j)这条路上所有山的喜恶度之和是（c，d）(a≤c≤d≤b)最大值。于是老师便向你请教，你能帮助他吗?值得注意的是，在《山海经》中，第i座山只能到达第i+1座山。
【输入】
输入格式(输入文件名hill．in)
输入第1行是两个数，n，m，2≤n≤100000，1≤m≤l00000，n表示一共有n座山，m表示老师想查询的数目。
第2行是n个整数，代表n座山的喜恶度，绝对值均小于10000。
以下m行每行有a，b两个数，1≤a≤j≤b≤m，表示第a座山到第b座山。
【输出】
输出格式(输出文件名hill.out)
一共有m行，，每行有3个数i，j，s，表示从第i座山到第j座山总的喜恶度为s。显然，对于每个查询，有a≤i≤j≤b，如果有多组解，则输出i最小的，如果i也相等，则输出j最小的解。
【输入输出样例】
输入(hill．in)
5 3
5 -6 3 -1 4
1 3
1 5
5 5
输出(hill．out)
1 1 5
3 5 6
5 5 4
推荐一个网址，讲得很好——>点击打开链接。
简单来说，就是对一个区间储存从左边开始的最值lm及其右端点lr，从右边开始的最值rm及其左端点rl，区间的和sum及区间左右端点l,r，还有区间的最值maxn及其左右端点ml,mr。传递的时候注意一下先后顺序，因为需要左端点尽量靠前。
Code：
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>#define root 1,1,n#define lchild rt<<1,l,mid#define rchild rt<<1|1,mid+1,rusing namespace std;struct point{int l,r,sum,lr,rl,lm,rm,maxn,ml,mr;}tree[800010];int n,m,a[100010];inline int in(){int x=0; char ch=getchar(); bool f=true;while (ch<'0' || ch>'9'){if (ch=='-') f=false;ch=getchar();}while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();if (!f) x=-x;return x;}inline void push_up(int rt,int l,int r){//l,r,sumtree[rt].l=l,tree[rt].r=r;tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum;//lmaxn,lrtree[rt].lm=tree[rt<<1].lm,tree[rt].lr=tree[rt<<1].lr;if (tree[rt<<1].sum+tree[rt<<1|1].lm>tree[rt].lm)tree[rt].lm=tree[rt<<1].sum+tree[rt<<1|1].lm,tree[rt].lr=tree[rt<<1|1].lr;//rmax,rltree[rt].rm=tree[rt<<1|1].rm,tree[rt].rl=tree[rt<<1|1].rl;if (tree[rt<<1|1].sum+tree[rt<<1].rm>=tree[rt].rm)tree[rt].rm=tree[rt<<1|1].sum+tree[rt<<1].rm,tree[rt].rl=tree[rt<<1].rl;//maxntree[rt].maxn=tree[rt<<1].maxn;tree[rt].ml=tree[rt<<1].ml,tree[rt].mr=tree[rt<<1].mr;if (tree[rt<<1].rm+tree[rt<<1|1].lm>tree[rt].maxn){tree[rt].maxn=tree[rt<<1].rm+tree[rt<<1|1].lm;tree[rt].ml=tree[rt<<1].rl,tree[rt].mr=tree[rt<<1|1].lr;}if (tree[rt<<1|1].maxn>tree[rt].maxn){tree[rt].maxn=tree[rt<<1|1].maxn;tree[rt].ml=tree[rt<<1|1].ml,tree[rt].mr=tree[rt<<1|1].mr;}}inline void build(int rt,int l,int r){if (l==r){int x=in();tree[rt].sum=tree[rt].lm=tree[rt].rm=tree[rt].maxn=x;tree[rt].l=tree[rt].r=tree[rt].lr=tree[rt].rl=tree[rt].ml=tree[rt].mr=l;return;}int mid=(l+r)>>1;build(lchild); build(rchild);push_up(rt,l,r);}inline point query(int rt,int l,int r,int ll,int rr){if (ll<=l && r<=rr) return (point)(tree[rt]);int mid=(l+r)>>1;if (rr<=mid) return query(lchild,ll,rr);else if(ll>mid) return query(rchild,ll,rr);else {point s1,s2,s;s1=query(lchild,ll,mid),s2=query(rchild,mid+1,rr);//l,r,sums.sum=s1.sum+s2.sum; s.l=s1.l,s.r=s2.r;//lmax,lrs.lm=s1.lm,s.lr=s1.lr;if (s1.sum+s2.lm>s.lm)s.lm=s1.sum+s2.lm,s.lr=s2.lr;//rmax,rls.rm=s2.rm,s.rl=s2.rl;if (s2.sum+s1.rm>=s.rm)s.rm=s2.sum+s1.rm,s.rl=s1.rl;//maxn,ml,mrs.maxn=s1.maxn,s.ml=s1.ml,s.mr=s1.mr;if (s1.rm+s2.lm>s.maxn)s.maxn=s1.rm+s2.lm,s.ml=s1.rl,s.mr=s2.lr;if (s2.maxn>s.maxn)s.maxn=s2.maxn,s.ml=s2.ml,s.mr=s2.mr;return s;}}int main(){freopen("hill.in","r",stdin);freopen("hill.out","w",stdout);n=in(),m=in();build(root);while (m–){int x=in(),y=in();point k=query(root,x,y);printf("%d %d %d\n",k.ml,k.mr,k.maxn);}return 0;}
我希望你能知道，我的心永远只为你跳动。
