Description

有一个长度为 (n)( (n le 10^5) ) 的序列，和 (m) （(m le10^5)）组询问

求出区间中最大子段和和两个端点的位置

Solution

就是个线段树，但是很难写

没啥解释的就是纪念一下自己觉得很满意

#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace yspm{
	inline int read()
	{
		int res=0,f=1; char k;
		while(!isdigit(k=getchar())) if(k=='-') f=-1;
		while(isdigit(k)) res=res*10+k-'0',k=getchar();
		return res*f;
	}
	const int N=1e5+10;
	int a[N],n,T;
	struct node{
		int l,r,lmax,rmax,sum,ms,sl,sr,lpos,rpos;
		#define l(p) t[p].l
		#define r(p) t[p].r
		#define sum(p) t[p].sum
		#define lmax(p) t[p].lmax
		#define lpos(p) t[p].lpos
		#define rmax(p) t[p].rmax
		#define rpos(p) t[p].rpos
		#define sl(p) t[p].sl
		#define sr(p) t[p].sr
		#define ms(p) t[p].ms 
	}t[N<<2];
	inline void push_up(int p)
	{
		if(lmax(p<<1)>=sum(p<<1)+lmax(p<<1|1)) lmax(p)=lmax(p<<1),lpos(p)=lpos(p<<1);
		else lmax(p)=sum(p<<1)+lmax(p<<1|1),lpos(p)=lpos(p<<1|1);
		
		if(rmax(p<<1|1)>sum(p<<1|1)+rmax(p<<1)) rmax(p)=rmax(p<<1|1),rpos(p)=rpos(p<<1|1);
		else rmax(p)=rmax(p<<1)+sum(p<<1|1),rpos(p)=rpos(p<<1);
		
		sum(p)=sum(p<<1)+sum(p<<1|1); ms(p)=-1e15-10;
		
		if(ms(p<<1)>ms(p)) ms(p)=ms(p<<1),sl(p)=sl(p<<1),sr(p)=sr(p<<1);
		
		if(ms(p<<1|1)>ms(p)) ms(p)=ms(p<<1|1),sl(p)=sl(p<<1|1),sr(p)=sr(p<<1|1);
		
		if(rmax(p<<1)+lmax(p<<1|1)>ms(p))
		{
			ms(p)=rmax(p<<1)+lmax(p<<1|1);
			sl(p)=rpos(p<<1); sr(p)=lpos(p<<1|1); 
		}
		return ;
	}
	inline void build(int p,int l,int r)
	{
		l(p)=l; r(p)=r; 
		if(l==r)
		{
			sum(p)= lmax(p)= rmax(p)=a[l]; 
			sl(p)=l; sr(p)=l;
			lpos(p)=rpos(p)=l; ms(p)=a[l]; 
			return ;
		}
		int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r);
		push_up(p);
		
		return ;
	}
	inline node query(int p,int l,int r)
	{
		
		if(l<=l(p)&&r(p)<=r) return t[p];
		int mid=(l(p)+r(p))>>1;
		if(r<=mid) return query(p<<1,l,r);
		if(l>mid) return query(p<<1|1,l,r);
		node ans,tl=query(p<<1,l,r),tr=query(p<<1|1,l,r);
		if(tl.rmax+tr.sum>=tr.rmax)
		{
			ans.rmax=tl.rmax+tr.sum; ans.rpos=tl.rpos;
		}else ans.rmax=tr.rmax,ans.rpos=tr.rpos;
		
		if(tl.lmax>=tl.sum+tr.lmax)
		{
			ans.lmax=tl.lmax; ans.lpos=tl.lpos;
		}else ans.lmax=tl.sum+tr.lmax,ans.lpos=tr.lpos;
 		
 		if(tl.ms>=tr.ms)
		{
			ans.ms=tl.ms; ans.sl=tl.sl; ans.sr=tl.sr;
		}else 
		{
			ans.ms=tr.ms; ans.sl=tr.sl; ans.sr=tr.sr;
		}
		if(tl.rmax+tr.lmax>ans.ms)
		{
			
			ans.ms=tl.rmax+tr.lmax; ans.sl=tl.rpos; ans.sr=tr.lpos;
		} 
		else if(tl.rmax+tr.lmax==ans.ms)
		{
			if(ans.sl>tl.rpos)
			{
				ans.sl=tl.rpos; ans.sr=tr.lpos;
			}
			else if(ans.sl==tl.rpos)
			{
				if(ans.sr>tr.lpos) ans.sr=tr.lpos;
			}
		}
		return ans;
	}
	signed main()
	{
		n=read(); T=read(); for(int i=1;i<=n;++i) a[i]=read(); build(1,1,n);
		
		while(T--)
		{
			int l=read(),r=read();
			node res=query(1,l,r);
			printf("%lld %lld %lld
",res.sl,res.sr,res.ms);
		}
		return 0;
	}
}
signed main(){return yspm::main();}