ls-526互联

#include<bits/stdc++.h>
#define int long long
#define f t[p]
#define ls p<<1
#define rs p<<1|1
using namespace std;
int n,m,a[100001];
struct aa
{
	int l,r,val,qz,qr,zz,zl,zr,hz,hl;
}t[400004];
aa hebing(aa a,aa b)
{
	aa p;
	if(a.l==0&&a.r==0&&b.l==0&&b.r==0) return aa{0,0,0,0,0,0,0,0,0,0};
	if(a.l==0&&a.r==0) return b;
	if(b.l==0&&b.r==0) return a;
	p.l=a.l,p.r=b.r;
	p.val=a.val+b.val;
	if(a.val+b.qz>a.qz) p.qz=a.val+b.qz,p.qr=b.qr;
	else p.qz=a.qz,p.qr=a.qr;
	if(b.val+a.hz>=b.hz) p.hz=b.val+a.hz,p.hl=a.hl;
	else p.hz=b.hz,p.hl=b.hl;
	int qjh=a.hz+b.qz;/*前加后*/
	if(a.zz>=qjh&&a.zz>=b.zz) p.zz=a.zz,p.zl=a.zl,p.zr=a.zr;
	else if(b.zz>qjh) p.zz=b.zz,p.zl=b.zl,p.zr=b.zr;
	else p.zz=qjh,p.zl=a.hl,p.zr=b.qr;
	return p;
}
void build(int p,int l,int r)
{
	f.l=l,f.r=r;
	if(l==r)
	{
		f.zz=f.val=f.qz=f.hz=a[l];
		f.qr=f.zl=f.zr=f.hl=l;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	f=hebing(t[ls],t[rs]);
}
aa ask(int p,int l,int r)
{
	aa tmp=aa{0,0,0,0,0,0,0,0,0,0};
	if(f.l>r||f.r<l) return tmp;
	if(f.l>=l&&f.r<=r) tmp=f;
	else tmp=hebing(ask(ls,l,r),ask(rs,l,r));
	return tmp;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		aa ans=ask(1,x,y);
		cout<<ans.zl<<" "<<ans.zr<<" "<<ans.zz<<"\n";
	}
}