记录编号	160134	评测结果	AWWWWWWW
题目名称	山海经	最终得分	12
用户昵称	wolf.	是否通过	未通过
代码语言	C++	运行时间	2.268 s
提交时间	2015-04-24 08:08:42	内存使用	0.31 MiB

#include<iostream>
#include<fstream>
#include<bitset>
#include<vector>
#include<deque>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdio>
using namespace std;
#if defined wolf
const string ok="OK";
const string kk="	";
ofstream nnew("hill.in",ios::app);
ifstream fin("hill.in");
#define fout cout
#define Endl endl
#else
ifstream fin("hill.in");
ofstream fout("hill.out");
#endif
class llink{
public:
	int x,y,n;
	llink(){
		x=-1;
		y=-1;
	}
	llink(int a,int b,int c){
		x=a;
		y=b;
		n=c;
	}
	llink plus(const llink a,const llink b){
		if(a.x==-1&&a.y==-1){
			return b;
		}
		if(b.x==-1&&b.y==-1){
			return a;
		}
		llink it(a.x,b.y,a.n+b.n);
		return it;
	}
	llink cmp(const llink a,const llink b){
		if(a.x==-1&&a.y==-1){
			return b;
		}
		if(b.x==-1&&b.y==-1){
			return a;
		}
		if(a.n<b.n){
			return b;
		}else{
			return a;
		}
		return llink();
	}
};

class node{
public:
	int l,r;
	llink sum,amx,lmx,rmx;
	node(){
		l=-1;
		r=-1;
	}
	node(int a,int b){
		l=a;
		r=b;
	}
	node(int a,int b,llink c,llink d,llink e,llink f){
		l=a;
		r=b;
		sum=c;
		amx=d;
		lmx=e;
		rmx=f;
	}
	node operator + (const node& p){
		if(l==-1&&r==-1){
			return p;
		}
		if(p.l==-1&&p.r==-1){
			return *this; 
		}
		node it(l,p.r);
		it.sum=llink().plus(sum,p.sum);
		it.amx=llink().cmp(amx,p.amx);
		if(rmx.x!=-1||p.lmx.x!=-1){
			it.amx=llink().cmp(it.amx,llink().plus(rmx,p.lmx));
		}
		it.lmx=llink().cmp(lmx,llink().plus(sum,p.lmx));
		it.rmx=llink().cmp(p.rmx,llink().plus(p.sum,rmx));
		return it;
	}
};
vector<int> num;//原始数据
vector<node> TT;
void build(int p,int l,int r){
	TT[p].l=l;
	TT[p].r=r;
	if(l==r){
		if(num[l]<0){
			TT[p].lmx=llink(0,0,0);
			TT[p].rmx=llink(0,0,0);
		}else if(num[l]==0){
			TT[p].lmx=llink(0,0,0);
			TT[p].rmx=llink(l,l,num[l]);
		}else{
			TT[p].lmx=llink(l,l,num[l]);
			TT[p].rmx=llink(l,l,num[l]);
		}
		TT[p].amx=llink(l,l,num[l]);
		TT[p].sum=llink(l,l,num[l]);
		//cout<<p<<kk<<TT[p].lmx.n<<kk<<TT[p].rmx.n<<kk<<TT[p].amx.n<<endl;
		return;
	}
	int mid=(l+r)/2;
	build(2*p,l,mid);
	build(2*p+1,mid+1,r);
	TT[p]=TT[p*2]+TT[p*2+1];
	//cout<<p<<kk<<TT[p].lmx.n<<kk<<TT[p].rmx.n<<kk<<TT[p].amx.n<<endl;
}
node find(int p,int a,int b){
	//cout<<p<<"  "<<a<<"  "<<b<<endl;
	if(TT[p].l==a&&TT[p].r==b){
		return TT[p];
	}
	int mid=(TT[p].l+TT[p].r)/2;
	if(b<=mid){
		return find(2*p,a,b);
	}else if(a>mid){
		return find(2*p+1,a,b);
	}else{
		return find(2*p,a,mid)+find(2*p+1,mid+1,b);
	}
}
int main(){
	double n,m;
	fin>>n>>m;
	TT.resize((int)(n*(log(n)/log(2.0))));
	for(int i=0;i!=(int)n;++i){
		int e;
		fin>>e;
		num.push_back(e);
	}
	build(1,0,num.size()-1);
	for(int i=0;i!=m;++i){
		int a,b;
		fin>>a>>b;
		node it;
		it=find(1,a-1,b-1);
		fout<<it.amx.x+1<<"  "<<it.amx.y+1<<"  "<<it.amx.n<<endl;
	}
	//-------------------------*/
	#if defined wolf
	cout<<endl<<(double)clock()/CLOCKS_PER_SEC<<'s'<<endl;
	#endif
	return 0;
}
//Designed by wolf
//Thu Apr 23 2015