记录编号	38440	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	4.659 s
提交时间	2012-04-18 21:08:16	内存使用	1.03 MiB

#include <fstream>
using namespace std;
ifstream fin("hill.in");
ofstream fout("hill.out");
int n,m,H[100004],Re[100004],Al,Ar,Max;
class Node
{
public:
    int Data,l,r,L,R;
    int Rdata,rdl;
    int Ldata,ldr;
    Node *lx,*rx;
	Node()
	{
		Data=0;
		l=0;r=0;L=0;R=0;
		Rdata=0;rdl=0;
		Ldata=0;ldr=0;
	}
}Root,lable;
void Build_IT(Node* p,int st,int en)
{
int mid;
    mid=(st+en)/2;
    p->L=st;p->R=en;
    if(st==en)
    {
        p->Data=H[st];       p->l=st;p->r=en;
        p->Rdata=H[st];      p->rdl=st;
        p->Ldata=H[st];      p->ldr=st;
        return;
    }
    else
    {
        p->lx=new Node;
        Build_IT(p->lx,st,mid);
        p->rx=new Node;
        Build_IT(p->rx,mid+1,en);
    /*最大值*/
        p->l=p->lx->rdl;
        p->r=p->rx->ldr;
        p->Data=p->lx->Rdata+p->rx->Ldata;
        if(p->Data < p->lx->Data)
            p->Data=p->lx->Data,p->l=p->lx->l,p->r=p->lx->r;
        if(p->Data < p->rx->Data)
            p->Data=p->rx->Data,p->l=p->rx->l,p->r=p->rx->r;
    /*左边值*/
        p->Ldata=max(Re[p->lx->ldr],Re[p->rx->ldr])-Re[st-1];
        p->ldr=(Re[p->lx->ldr] > Re[p->rx->ldr] ? p->lx->ldr : p->rx->ldr);
    /*右边值*/
        p->Rdata=max(Re[en]-Re[p->lx->rdl-1],Re[en]-Re[p->rx->rdl-1]);
        p->rdl=(Re[en]-Re[p->lx->rdl-1] > Re[en]-Re[p->rx->rdl-1] ? p->lx->rdl : p->rx->rdl);
    }
}
 
void Initialize()
{
int i;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>H[i];
        Re[i]=Re[i-1]+H[i];
    }
    Build_IT(&Root,1,n);
}
 
void F(Node *p,int st,int en)
{
    if(p->L==st && p->R==en)
    {
	Node *temp=new Node;temp->Data=-10000000;temp->lx=&lable;temp->rx=p;
		if(lable.rdl==0)
		{
			lable=*p;
			return;
		}
    /*最大值*/
        temp->l=temp->lx->rdl;
        temp->r=temp->rx->ldr;
        temp->Data=temp->lx->Rdata+temp->rx->Ldata;
        if(temp->Data < temp->lx->Data)
            temp->Data=temp->lx->Data,temp->l=temp->lx->l,temp->r=temp->lx->r;
		else
			if(temp->Data == temp->lx->Data && (temp->l > temp->lx->l || (temp->l==temp->lx->l && temp->r > temp->lx->r)))
				temp->Data=temp->lx->Data,temp->l=temp->lx->l,temp->r=temp->lx->r;
        if(temp->Data < temp->rx->Data)
            temp->Data=temp->rx->Data,temp->l=temp->rx->l,temp->r=temp->rx->r;
		else
			if(temp->Data == temp->rx->Data && (temp->l > temp->rx->l || (temp->l==temp->rx->l && temp->r > temp->rx->r)))
				temp->Data=temp->rx->Data,temp->l=temp->rx->l,temp->r=temp->rx->r;
    /*左边值*/
        temp->Ldata=max(Re[temp->lx->ldr],Re[temp->rx->ldr])-Re[st-1];
        temp->ldr=(Re[temp->lx->ldr] > Re[temp->rx->ldr] ? temp->lx->ldr : temp->rx->ldr);
    /*右边值*/
        temp->Rdata=max(Re[en]-Re[temp->lx->rdl-1],Re[en]-Re[temp->rx->rdl-1]);
        temp->rdl=(Re[en]-Re[temp->lx->rdl-1] > Re[en]-Re[temp->rx->rdl-1] ? temp->lx->rdl : temp->rx->rdl);
		
		lable=*temp;
	}
    else
    {
        int Mid=(p->L+p->R)/2;
        if(Mid>=en || Mid<st)
        {
            if(Mid>=en)
                F(p->lx,st,en);
            else
                F(p->rx,st,en);
        }
        else
        {
            F(p->lx,st,Mid);
            F(p->rx,Mid+1,en);
        }
    }
}
 
void Solve()
{
int i,St,En;Node *p;
    for(i=1;i<=m;i++)
    {
        fin>>St>>En;
        Max=-210000000;
        p=new Node;lable=*p;lable.Data=-100000000;
        F(&Root,St,En);
		if(Re[lable.r-1]-Re[lable.l-1]==lable.Data)
			lable.r--;
        fout<<lable.l<<" "<<lable.r<<" "<<lable.Data<<endl;
    }
}
 
int main()
{
    Initialize();
     
    Solve();
     
    fin.close();
    fout.close();
    return 0;
}