本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-25 20:23:26

题意：

给出长度为 $n$ 的数组 $a$ ，求三元组最大和，满足三元组严格升序且后两者差大于前两者差。

用 $(I,J,K)$ 分别表示其对应三元组中哪一个元素，考虑有效的点对 $(i,j)$ 个数。

发现对于每一个区间内的答案所对应的 $(i,j)$ 一定为一个子区间内的最大与次大值。

对于区间 $[i,j]$ ，若无右端点限制，这个区间内的 $(I,J)$ 最优值一定为最大与次大值。原因显然。

而所有区间的最大值与次大值点对数的数量级是 $\mathrm{O(n)}$ 的。（相同数值按照下标定优先级）

这里的证明可以考虑单调栈过程。寻找这些对也可以直接通过单调栈求解。

然后我们现在得到了 $\mathrm{O(n)}$ 对点对。怎么求答案呢。

我们可以把询问离线下来，按照下标顺序依次将点对丢进集合处理其对答案贡献。

可以这样维护：

枚举左端点，计算每一个位置作为 $k$ 的答案。所有以当前点为 $I$ 的点对 $(i,j)$ 对每一个合法位置造成的贡献。合法位置是一个后缀。

设 $b_x$ 表示上面说的以 $x$ 为 $K$ 的最大贡献，这个贡献的格式是 $b_x=max(b_x,a_x+val)$ ，后面的 $val$ 是 $a_i+a_j$ ，对同一对点对 $(i,j)$ 是定值。这个可以直接线段树维护。查询就直接区间最值即可。

int pre[N],suf[N];

int stk[N],tot;
int a[N];

struct Seg_Tree{
	int t[N<<2],mx[N<<2];
	int tag[N<<2];
	void pushup(int x){
		t[x]=max(t[ls],t[rs]);
		t[x]=max(t[x],mx[x]+tag[x]);
	}
	void pushdown(int x){
		if(tag[ls]<tag[x]){
			tag[ls]=tag[x];
			t[ls]=max(t[ls],mx[ls]+tag[ls]);
		}
		if(tag[rs]<tag[x]){
			tag[rs]=tag[x];
			t[rs]=max(t[rs],mx[rs]+tag[rs]);
		}
	}
	void update(int x,int l,int r,int L,int R,int val){
		if(L<=l&&r<=R){
			tag[x]=max(tag[x],val);
			t[x]=max(t[x],tag[x]+mx[x]);
		}else{
			pushdown(x);
			if(L<=mid)
				update(ls,l,mid,L,R,val);
			if(R>mid)
				update(rs,mid+1,r,L,R,val);
			pushup(x);
		}
	}
	int query(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R)
			return t[x];
		pushdown(x);
		int ans=0;
		if(L<=mid)
			ans=max(ans,query(ls,l,mid,L,R));
		if(R>mid)
			ans=max(ans,query(rs,mid+1,r,L,R));
		return ans;
	}
	void build(int x,int l,int r){
		tag[x]=0;
		if(l==r)
			t[x]=mx[x]=a[l];
		else{
			build(ls,l,mid);
			build(rs,mid+1,r);
			mx[x]=max(mx[ls],mx[rs]);
		}
	}
}T;

pir p[N<<1];

struct Que{
	int l,r,id;
	bool operator<(Que &ano)const{
		return l>ano.l;
	}
}Q[N];

int ans[N];

signed main(){
	int n=read(),q=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++){
		while(tot>0&&a[stk[tot]]<a[i])
			suf[stk[tot--]]=i;
		pre[i]=stk[tot];
		stk[++tot]=i;
	}
	for(int i=1;i<=n;i++){
		if(pre[i])
			p[++tot]={pre[i],i};
		if(suf[i])
			p[++tot]={i,suf[i]};
	}
	sort(p+1,p+1+tot);
	for(int i=1;i<=q;i++)
		Q[i]={read(),read(),i};
	sort(Q+1,Q+1+q);
	T.build(1,1,n);
	for(int l=n,nw=tot,nwq=1;l>=1&&nw>=1;l--){
		while(p[nw].fi==l){
			int L=p[nw].se+(p[nw].se-p[nw].fi),R=n;
			nw--;
			if(L>R)
				continue;
			T.update(1,1,n,L,R,a[p[nw+1].fi]+a[p[nw+1].se]);
		}
		while(Q[nwq].l==l){
			ans[Q[nwq].id]=T.query(1,1,n,Q[nwq].l,Q[nwq].r);
			nwq++;
		}
	}
	for(int i=1;i<=q;i++)
		print(ans[i]),pc('\n');
	return 0;
}