记录编号	433279	评测结果	AAAAAAAA
题目名称	山海经	最终得分	100
用户昵称	Hzoi_moyi	是否通过	通过
代码语言	C++	运行时间	0.744 s
提交时间	2017-08-05 09:37:38	内存使用	15.96 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int sj=100010;
int n,m,li[sj],ans,zb,yb,zi,yi,zj,yj,vi;
struct node
{
     int l,r,v;
     int al,ar,a;
     int zj,yj,zm,ym;
}t[sj*4];
void build(int x,int l,int r)
{
     t[x].l=l,t[x].r=r;
     if(l==r)
     {
        t[x].v=t[x].a=t[x].zm=t[x].ym=li[l];
        t[x].al=t[x].ar=t[x].zj=t[x].yj=l;
        return;
     }
     int mid=(l+r)>>1,ls=x<<1,rs=(x<<1)|1;
     build(ls,l,mid),build(rs,mid+1,r);
     t[x].v=t[ls].v+t[rs].v;
     int temp=t[ls].ym+t[rs].zm;
     if(t[ls].a>=t[x].a)
        t[x].a=t[ls].a,t[x].al=t[ls].al,t[x].ar=t[ls].ar;
     if(temp>t[x].a)
         t[x].a=temp,t[x].al=t[ls].yj,t[x].ar=t[rs].zj;
     if(t[rs].a>t[x].a)   
        t[x].a=t[rs].a,t[x].al=t[rs].al,t[x].ar=t[rs].ar;
     t[x].zm=t[ls].zm,t[x].zj=t[ls].zj;
     t[x].ym=t[rs].ym,t[x].yj=t[rs].yj;
     if(t[ls].ym+t[rs].v>t[x].ym)
          t[x].ym=t[ls].ym+t[rs].v,t[x].yj=t[ls].yj;
     if(t[rs].zm+t[ls].v>=t[x].zm)
          t[x].zm=t[rs].zm+t[ls].v,t[x].zj=t[rs].zj;
}
int query(int x,int y,int z)
{
    if(y<=t[x].l&&z>=t[x].r)
    {
        zb=t[x].al,yb=t[x].ar;
        zi=t[x].zm,yi=t[x].ym;
        zj=t[x].zj,yj=t[x].yj;
        vi=t[x].v;
        return t[x].a;
    }
    int mid=(t[x].l+t[x].r)>>1;
    if(z<=mid) return query(x<<1,y,z);
    if(y>mid)  return query((x<<1)|1,y,z);
    int ans1=query(x<<1,y,z);
    int jlz1=zi,jly1=yi,ljz1=zj,ljy1=yj,l11=zb,l12=yb,zv1=vi;
    int ans2=query((x<<1)|1,y,z);
    int jlz2=zi,jly2=yi,ljz2=zj,ljy2=yj,l21=zb,l22=yb,zv2=vi;
    int ansz=jly1+jlz2;
    zi=jlz1,zj=ljz1,yi=jly2,yj=ljy2;
    if(jlz2+zv1>zi)  zi=jlz2+zv1,zj=ljz2;
    if(jly1+zv2>=yi)  yi=jly1+zv2,yj=ljy1;
    if(ans1>=ans2&&ans1>=ansz)
    {
        zb=l11,yb=l12;
        return ans1;
    }
    if(ansz>=ans2)
    {
        zb=ljy1,yb=ljz2;
        return ansz;
    }
    zb=l21,yb=l22;
    return ans2;
}
int main()
{
    //freopen("t.txt","r",stdin);
    freopen("hill.in","r",stdin);
    freopen("hill.out","w",stdout);
    memset(t,-0x7f,sizeof(t));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&li[i]);
    build(1,1,n);
    int a1,a2;
    for(int i=1;i<=m;i++)
    {
       scanf("%d%d",&a1,&a2);
       ans=query(1,a1,a2);
       while(li[yb]==0) yb--;
       printf("%d %d %d\n",zb,yb,ans);
    }
    //while(1);
    return 0;
}