记录编号	159578	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.203 s
提交时间	2015-04-21 21:15:16	内存使用	13.66 MiB

#include<cstdio>
#include<iostream>
using namespace std;
int n,m,a[100001],d[100000]={0},tot=1,maxn=0xffffff;
#define Nil NULL
#define max(a,b) (((a)<(b))?(b):(a))
class poi
{
public:
	int l;int r;int s;
	poi()
	{
		l=maxn,r=maxn,s=0;
	}
	poi(int l_,int r_,int s_){l=l_,r=r_,s=s_;}
};
inline bool empty(const poi &a){
	return a.l==maxn;
}
inline bool operator < (const poi &a,const poi &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 poi operator + (const poi &a,const poi &b)
{
	if(empty(a)) return b;
	if(empty(b)) return a;
	poi c;
	c.l=a.l;c.r=b.r;c.s=b.s+a.s;
	return c;
}
poi ma(poi a,poi b)
{
	poi c;
	if(a<b)
		return b;
	else
		return a;
}
class miku
{
public:
	poi lmx;poi rmx;poi ls;poi sum;
	miku(){}
	miku(int x,int t){
		sum=poi(x,x,t);
		ls=poi(x,x,t);
		if(t>0) lmx=poi(x,x,t);
		else lmx=poi();
		if(t>=0) rmx=poi(x,x,t);
		else rmx=poi();
	}
};
inline bool empty(const miku &d){
	return empty(d.sum);
}
inline miku operator + (const miku &a,const miku &b)
	{
	if(empty(a)) return b;
	if(empty(b)) return a;
	miku c;
	c.sum=a.sum+b.sum;
	c.ls=ma(a.ls,b.ls);
	if(!empty(a.rmx)||!empty(b.lmx)) c.ls=ma(c.ls,a.rmx+b.lmx);//情况2:越过了中线
	c.lmx=ma(a.lmx,a.sum+b.lmx);
	c.rmx=ma(b.rmx,a.rmx+b.sum);
	return c;
}
poi add(int x,int y,int z)
{
	poi q;
	q.l=x;q.r=y;q.s=z;
	return q;
}
class xdt
{
public:
	miku a;
	int right;int left;int l;int r;
}t[200000];
int make(int l,int r)
{
	int mid=(l+r)/2,root=tot;
	t[root].l=l;t[root].r=r;
	if(l==r)
	{
		if(a[l]>0)
		{
		t[root].a.lmx=add(l,r,a[l]);
		t[root].a.rmx=add(l,r,a[l]);
		}
		t[root].a.sum=add(l,r,a[l]);t[root].right=-1;t[root].left=-1;
	}
	else
	{
		t[root].left=++tot;make(l,mid);t[root].right=++tot;make(mid+1,r);
		t[root].a=t[t[root].left].a+t[t[root].right].a;
	}
	return 0;
}
poi find(int root,int l,int r)
{
	poi c;
	if(l>t[root].r||r<t[root].l)
		return c;
	if(l>=t[root].l&&r<=t[root].r)
		return t[root].a.ls;
	else
		return find(t[root].left,l,r)+find(t[root].right,l,r);
}
class Node{
public:
	int l,r;
	miku 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 miku query(int a,int b){
		if(a>r||b<l) return miku();
		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=miku(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);
		miku d=root->query(a,b);
		poi a=d.ls;
		printf("%d %d %d\n",a.l,a.r,a.s);
	}
	return 0;
}