记录编号	159588	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	3.631 s
提交时间	2015-04-21 22:09:10	内存使用	0.43 MiB

#include <fstream>
#include <queue>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
ifstream in("hill.in");
ofstream out("hill.out");
/*#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;
}*/

int n,q,A[100001]={0};
const int INF=0x7ffffff;
class Orz
{
public:
	int l;
	int r;
	int s;
	Orz()
	{
		l=r=INF;
		s=0;
	}
	Orz(int ll,int rr,int ss)
	{
		l=ll;
		r=rr;
		s=ss;
	}
};
bool operator <(const Orz & a,const Orz & 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;
}
bool empty(const Orz a)
{
	return a.l==INF;
}
Orz operator +(const Orz & a,const Orz & b)
{
	if(empty(a))return b;
	if(empty(b))return a;
	Orz c;
	c.l=a.l;
	c.r=b.r;
	c.s=a.s+b.s;
	return c;
}
class tree
{
public:
	Orz sum,mmx,lmx,rmx;
	tree(){}
	tree(int s,int t)
	{
		sum=Orz(s,s,t);
		mmx=Orz(s,s,t);
		if(t>0)lmx=Orz(s,s,t);
		else lmx=Orz();
		if(t>=0)rmx=Orz(s,s,t);
		else rmx=Orz();
	}
};
bool empty(const tree & a)
{
	return empty(a.sum);
}
tree operator +(const tree & a,const tree & b)
{
	if(empty(a))return b;
	if(empty(b))return a;
	tree c;
	c.sum=a.sum+b.sum;
	c.mmx=max(a.mmx,b.mmx);
	if(!empty(a.rmx)||!empty(b.lmx))
	{
		c.mmx=max(c.mmx,a.rmx+b.lmx);
	}
	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;
	tree key;
	node *lc,*rc;
	node()
	{
		l=r=0;
		lc=rc=NULL;
	}
	void push_up()
	{
		if(lc!=NULL)
		{
			key=lc->key+rc->key;
		}
	}
	tree query(int a,int b)
	{
		if(a>r||b<l)return tree();
		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=tree(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;
}
node *root;
int main()
{
	int i,j,l,r;
	in>>n>>q;
	for(i=1;i<=n;i++)in>>A[i];
	root=build(A,1,n);
	for(i=1;i<=q;i++)
	{
		in>>l>>r;
		//out<<l<<' '<<r<<endl;
		tree d=root->query(l,r);
		Orz a=d.mmx;
		out<<a.l<<' '<<a.r<<' '<<a.s<<endl;
	}
	return 0;
}