Sicily 1136. 山海经

山海经"/>

Sicily 1136. 山海经

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

“南山之首曰鹊山。其首曰招摇之山，临于西海之上，多桂，多金玉。有草焉，其状如韭而青华，其名曰祝余，食之不饥……

又东三百里，曰堂庭之山，多δ荆喟自常嗨瘢嗷平稹

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

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

Input

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

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

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

Output

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

Sample Input

5 35 -6 3 -1 41 31 55 5

Sample Output

1 1 53 5 65 5 4

Problem Source

Jericho

转自：

// Problem#: 1136
// Submission#: 3586681
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: .0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include<iostream>
#include<algorithm>
#include<stdio.h>
#define RANGE 100005
#define INF 0x7fffffff
using namespace std;
struct node
{int l,r,sum;            //当前节点左边界、右边界、元素总和int lmn,rmn,lmax,rmax;  //从左边界开始连续到第lmn位置元素和，有最大值lmax//从右边界开始连续到第rmn位置元素和，有最大值rmaxint lson,rson;          //节点左儿子和右儿子的编号int sl,sr,smax;         //当前序列从sl到sr能取得最大连续值smax
}nn[RANGE*6];               //输入的线段树需要的空间为2*N（开3*N的数组)，计算时建立新树，故翻倍
int n,m,a[RANGE*2];
int nnum;                   //每次解决查询时，建立新的线段树节点的开始下标void computeMax(int index, int ls, int rs)//计算index节点的sum,sl,sr,smax,lmn,lmax,rmn,rmax
{int tmp;nn[index].sum=nn[ls].sum+nn[rs].sum;nn[index].smax=nn[ls].smax;nn[index].sl=nn[ls].sl;nn[index].sr=nn[ls].sr;tmp=nn[ls].rmax+nn[rs].lmax;if(tmp>nn[index].smax || (tmp==nn[index].smax && nn[ls].rmn<nn[index].sl)){nn[index].smax=nn[ls].rmax+nn[rs].lmax;nn[index].sl=nn[ls].rmn;nn[index].sr=nn[rs].lmn;}if(nn[rs].smax>nn[index].smax){nn[index].smax=nn[rs].smax;nn[index].sl=nn[rs].sl;nn[index].sr=nn[rs].sr;}//计算当前节点的lmax与rmaxtmp=nn[ls].sum+nn[rs].lmax;if(tmp>nn[ls].lmax){nn[index].lmax=tmp;nn[index].lmn=nn[rs].lmn;}else{nn[index].lmax=nn[ls].lmax;nn[index].lmn=nn[ls].lmn;}tmp=nn[rs].sum+nn[ls].rmax;if(tmp>=nn[rs].rmax)//注意等于号{nn[index].rmax=tmp;nn[index].rmn=nn[ls].rmn;}else{nn[index].rmax=nn[rs].rmax;nn[index].rmn=nn[rs].rmn;}
}
int compute(int l, int r, int index)
{if(l==nn[index].l && r==nn[index].r)return index;int ls=index*2;     //左二子标号int rs=index*2+1;   //右儿子标号if(r<=nn[ls].r)return compute(l,r,ls);else if(l>=nn[rs].l)return compute(l,r,rs);else{int nindex=nnum++;nn[nindex].l=l; nn[nindex].r=r;nn[nindex].lson=compute(l,nn[ls].r,ls);nn[nindex].rson=compute(nn[ls].r+1,r,rs);computeMax(nindex, nn[nindex].lson, nn[nindex].rson);return nindex;}
}
void buildTree(int l, int r, int index)
{nn[index].l = l;nn[index].r = r;if(l==r){nn[index].sum=nn[index].smax=nn[index].lmax=nn[index].rmax=a[l];nn[index].lmn=nn[index].rmn=nn[index].sl=nn[index].sr=l;return;}int mid=(l+r)/2;int ls,rs;   //左右儿子编号ls=index*2; rs=index*2+1;buildTree(l,mid,ls);buildTree(mid+1,r,rs);computeMax(index, ls, rs);
}
int main()
{//freopen("in","r",stdin);//freopen("out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%d",&a[i]);buildTree(1,n,1);for(int i=1;i<=m;++i){int tmpa,tmpb;scanf("%d%d",&tmpa,&tmpb);nnum=3*n+1;int nindex = compute(tmpa,tmpb,1);printf("%d %d %d\n", nn[nindex].sl, nn[nindex].sr, nn[nindex].smax);}
}