自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 22:46:57，当前版本为作者最后更新于2023-05-01 21:40:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

一道简单题，提供一种不需要脑子的做法。

首先题目问的是 $\max_{l\le u<v \le r \& a_u>a_v} a_u \times a_v$。后文称这是 $u$ 和 $v$ 的配对。

然后考虑如果 $l \le u < v \le r$ 时，如果出现了 $a_u<a_v$，那么最终答案肯定不是 $u$ 和 $v$ 之后的配对，不然换 $v$ 根他们配对更优。

所以对于每个数 $i$，它只会和第一个不比它小的数之前的一部分进行配。也就是说，用单调栈找到后面的第一个不比它小的数 $nxt_i$，最终 $u$ 只能和 $(u,nxt_u)$ 中的数配对。最优情况肯定是选中间的最大值。

那么考虑询问的时候，从 $l$ 出发，每次找到下一个 $k=nxt_l$。由定义，$(l,k)$ 中的数肯定比 $a_l$ 都小，也都比 $a_k$ 小，他们一定不会作为答案配对的前者，不然换 $l$ 会更优。

所以要么用 $l$ 和 $(l,k)$ 之间的数配对，这个可以预处理。要么看 $k$ 和后面的情况，令 $l=k$。

这个过程可以看做每个 $l$ 向 $nxt_l$ 连边然后找树链的最大值。可以倍增解决。

复杂度 $O(n \log n)$。

代码：

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,nxt[MAXN][30],mx[MAXN][30],st[MAXN][30],a[MAXN],q;
stack<int> sts; int calc(int l,int r) {if(l>r) return 0;int k=log2(r-l+1);return max(st[l][k],st[r-(1<<k)+1][k]);}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n; ffor(i,1,n) cin>>a[i],st[i][0]=a[i];
	ffor(k,1,20) for(int l=1,r=(1<<k);r<=n;l++,r++) st[l][k]=max(st[l][k-1],st[l+(1<<k-1)][k-1]);
	a[n+1]=INT_MAX; sts.push(n+1);
	ffor(i,0,21) nxt[n+1][i]=n+1;
	roff(i,n,1) {
		while(a[sts.top()]<a[i]) sts.pop();
		nxt[i][0]=sts.top(),mx[i][0]=a[i]*calc(i+1,nxt[i][0]-1);	
		ffor(j,1,20) nxt[i][j]=nxt[nxt[i][j-1]][j-1],mx[i][j]=max(mx[i][j-1],mx[nxt[i][j-1]][j-1]);
		sts.push(i);
	}
	cin>>q;
	ffor(i,1,q) {
		int l,r; cin>>l>>r;
		int ans=0;
		roff(j,20,0) if(nxt[l][j]<=r) ans=max(ans,mx[l][j]),l=nxt[l][j];
		ans=max(ans,a[l]*calc(l+1,r));
		cout<<ans<<'\n';	
	}
	return 0;
}