记录编号	159408	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.875 s
提交时间	2015-04-21 12:40:52	内存使用	0.70 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int INF=0x7fffffff/2;
#define Nil NULL
#define max(a,b) (((a)<(b))?(b):(a))
template<typename T> inline void update_max(T &a,const T &b){
	if(b>a) a=b;
}
class Dale{//Over hills, over dales, as we hit the dusty trails...^_^
public:
	int l,r,s;
	Dale(){l=r=INF;s=0;}
	Dale(int l_,int r_,int s_){l=l_,r=r_,s=s_;}
};
inline bool empty(const Dale &a){
	return a.l==INF;
}
inline bool operator < (const Dale &a,const Dale &b){//a劣于b?
	if(a.s!=b.s) return a.s<b.s;
	if(a.l!=b.l) return a.l>b.l;
	return a.r>b.r;
}
inline Dale operator + (const Dale &a,const Dale &b){
	if(empty(a)) return b;
	if(empty(b)) return a;
	Dale c;
	c.l=a.l;
	c.r=b.r;
	c.s=a.s+b.s;
	return c;
}
class Data{
public:
	Dale sum;
	Dale amx;//这个不能是空的......
	Dale lmx,rmx;
	Data(){}
	Data(int x,int t){
		sum=Dale(x,x,t);
		amx=Dale(x,x,t);
		//在拼合时,我们希望lmx尽量短而rmx尽量长
		if(t>0) lmx=Dale(x,x,t);
		else lmx=Dale();
		if(t>=0) rmx=Dale(x,x,t);
		else rmx=Dale();
	}
};
inline bool empty(const Data &d){
	return empty(d.sum);
}
inline Data operator + (const Data &a,const Data &b){
	if(empty(a)) return b;
	if(empty(b)) return a;
	Data c;
	c.sum=a.sum+b.sum;
	c.amx=max(a.amx,b.amx);//情况1:没有越过中线
	if(!empty(a.rmx)||!empty(b.lmx)) c.amx=max(c.amx,a.rmx+b.lmx);//情况2:越过了中线
	c.lmx=max(a.lmx,a.sum+b.lmx);
	c.rmx=max(b.rmx,a.rmx+b.sum);
	return c;
}
class Node{
public:
	int l,r;
	Data key;
	Node *lc,*rc;
	Node(){l=r=0;lc=rc=Nil;}
	inline void push_up(void){
		if(lc!=Nil){
			key=lc->key+rc->key;
		}
	}
	inline Data query(int a,int b){
		if(a>r||b<l) return Data();
		if(l>=a&&r<=b) return key;
		return lc->query(a,b)+rc->query(a,b);
	}
};
Node* build(int a[],int x,int y){
	Node *p=new Node();
	p->l=x,p->r=y;
	if(x==y) p->key=Data(x,a[x]);
	else{
		int mid=(x+y)/2;
		p->lc=build(a,x,mid);
		p->rc=build(a,mid+1,y);
		p->push_up();
	}
	return p;
}
const int SIZEN=100010;
Node *root;
int N,M;
int A[SIZEN]={0};
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
}
int main(){
	freopen("hill.in","r",stdin);
	freopen("hill.out","w",stdout);
	read();
	root=build(A,1,N);
	int a,b;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&a,&b);
		Data d=root->query(a,b);
		Dale a=d.amx;
		printf("%d %d %d\n",a.l,a.r,a.s);
	}
	return 0;
}