法阵

题意

给你一个长 \(n\) 的数列，有 \(t\) 次询问，每次询问区间 \([l,r]\) 里满足 \(l\le x<y<z \le r,y-x\le z-y\) 的三元组 \(a_x+a_y+a_z\) 的最大值。其中 \(n,t\leq 5\times 10^5\)。

solution

结论：最终对答案有贡献的二元组 \((x,y)\) 一定满足
\(a_x> \max_{i=x+1}^{y-1}(a_i),a_y> \max_{i=x+1}^{y-1}(a_i)\)。

证明：若存在 \(x<b<y,a_b>a_x \text{或} a_b>a_y\)，那么选择二元组 \((x,b)\) 或 \((b,y)\) 一定更优。

这样合法的二元组一共有 \(O(n)\) 个。

我们使用单调队列找出它们。

从左往右加入 \(a_i\)，维护单调递减的队列。因为一个数仍在单调队列中就说明它后面暂时没有比它大的元素，那么新增合法二元组 \((\text{踢出的元素},i)\) 和 \((\text{剩下的元素},i)\)。

找到合法二元组后，对于每一个二元组，我们都可以 ST 表或树状数组或线段树 \(O(\log n)\) 找出最优的 \(z\)。

这样就可以解决仅询问区间 \([1,n]\) 的问题。

但是我们有 \(t\) 次询问！考虑将询问离线下来，按左端点从大到小排序，在不考虑右端点的情况下，此时我们加入一些可能用上的二元组。记 \(ans_i\) 表示以 \(z=i\) 的目前的答案，\(ans_i= \max (\text{已加入的合法二元组})+a_i\)。用线段树维护 \(ans\)。我们加入一个二元组就相当于给 \(ans\) 的一个后缀都进行一次 \(\max\) 的操作，可以线段树区间修改，每次询问即在线段树上查找区间 \([l+2,r]\)。

总时间复杂度 \(O(n\log n)\)。

code

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
#define il inline
//#define int ll
using namespace std;
typedef long long ll;
const int N=5e5+7,mod=998244353;
int n,t;
ll a[N];
struct Q{ int id,l,r; }q[N];
bool cmp(Q a,Q b){ return a.l>b.l; }
vector<int> vec[N];
ll st[N];
int top;
ll ans[N];
ll tree[N<<2];
ll tag[N<<2];
ll stb[30][N];
int lg[N];
void pushdown(int u,int l,int r){
	int mid=(l+r)>>1;
	if(tag[u]>tag[u*2]){
		tree[u*2]=max(tree[u*2],tag[u]+max(stb[lg[mid-l+1]][l],stb[lg[mid-l+1]][mid-(1<<lg[mid-l+1])+1]));
		tag[u*2]=max(tag[u*2],tag[u]);
	}
	if(tag[u]>tag[u*2+1]){
		tree[u*2+1]=max(tree[u*2+1],tag[u]+max(stb[lg[r-(mid+1)+1]][mid+1],stb[lg[r-(mid+1)+1]][r-(1<<lg[r-(mid+1)+1])+1]));
		tag[u*2+1]=max(tag[u*2+1],tag[u]);
	}
}
void pushup(int u){
	tree[u]=max(tree[u*2],tree[u*2+1]);
}
void insert(int u,int l,int r,ll w,int x) {
	if(l>=x){
		tree[u]=max(tree[u],w+max(stb[lg[r-l+1]][l],stb[lg[r-l+1]][r-(1<<lg[r-l+1])+1]));
		tag[u]=max(tag[u],w);
		return;
	}
	int mid=(l+r)>>1;
	pushdown(u,l,r);
	if(mid>=x) insert(u*2,l,mid,w,x);
	insert(u*2+1,mid+1,r,w,x);
	pushup(u);
}
void build(int u,int l,int r){
	if(l==r) {
		if(l>=3)
		tree[u]=a[l]+a[l-1]+a[l-2];
		return;
	}
	int mid=(l+r)>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
	pushup(u);
}
ll ask(int u,int l,int r,int L,int R){
	if(l>=L&&r<=R){
		return tree[u];
	}
	int mid=(l+r)>>1;
	pushdown(u,l,r);
	ll mx=0;
	if(mid>=L) mx=max(mx,ask(u*2,l,mid,L,R));
	if(mid+1<=R) mx=max(mx,ask(u*2+1,mid+1,r,L,R));
	pushup(u);
	return mx;
}
int main(){
//	freopen("ex_fz1.in","r",stdin);
	freopen("fz.in","r",stdin);
	freopen("fz.out","w",stdout);
	sf("%d",&n);
	for(int i=2;i<=n;i++){
		lg[i]=lg[i>>1]+1;
	}
	for(int i=1;i<=n;i++) sf("%lld",&a[i]),stb[0][i]=a[i];
	for(int i=1;i<=lg[n];i++){
		for(int j=1;j+(1<<i)-1<=n;j++){
			stb[i][j]=max(stb[i-1][j],stb[i-1][j+(1<<(i-1))]);
		}
	}
	for(int i=1;i<=n;i++){
		while(top&&a[st[top]]<a[i])
			vec[st[top--]].push_back(i);
		for(int j=1;j<=top;j++){
			vec[st[j]].push_back(i);
		}
		st[++top]=i;
	}
	sf("%d",&t);
	for(int i=1;i<=t;i++) { sf("%d%d",&q[i].l,&q[i].r); q[i].id=i; }
	sort(q+1,q+t+1,cmp);
	build(1,1,n);
	for(int i=1;i<=t;i++){
		for(int j=q[i].l;j<=(i==1?n:q[i-1].l-1);j++){
			for(int x:vec[j]){
				if(x+x-j<=n)
				insert(1,1,n,a[j]+a[x],x+x-j);
			}
		}
		ans[q[i].id]=ask(1,1,n,q[i].l+2,q[i].r);
	}
	for(int i=1;i<=t;i++) pf("%lld\n",ans[i]);
}