自动搬运

查看原文

来自洛谷，原作者为

	konyakest **

搬运于2025-08-24 23:15:37，当前版本为作者最后更新于2025-05-10 15:43:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

挑战最短代码。

显然，原问题等价于求出每个区间的次大值下标。于是我们可以打表观察区间次大值的结构。

例如，当 $a=[2,8,1,5,9,6,3,7,4]$ 时，我们可以打出以下表：（第 $i$ 行第 $j$ 列表示区间 $[i,j]$ 的次大值下标，若不存在则为 $0$）。

0 1 1 4 2 2 2 2 2
0 0 3 4 2 2 2 2 2
0 0 0 3 4 6 6 8 8
0 0 0 0 4 6 6 8 8
0 0 0 0 0 6 6 8 8
0 0 0 0 0 0 7 6 6
0 0 0 0 0 0 0 7 9
0 0 0 0 0 0 0 0 9
0 0 0 0 0 0 0 0 0

观察发现，每个元素最多占据两个矩形区域。下文中用 $[a,b]\times [c,d]$ 的形式表示一个矩形区域。

证明：

考虑一个元素何时成为区间次大值。

设 $pre_i$ 表示 $i$ 前面最后一个比 $a_i$ 大的位置，$prepre_i$ 表示 $i$ 前面倒数第二个比 $a_i$ 大的位置；$nxt_i$ 表示 $i$ 后面最前一个比 $a_i$ 大的位置，$nxtnxt_i$ 表示 $i$ 后面第二个比 $a_i$ 大的位置。

则 $i$ 成为次大值的区域为：

$$[prepre_i+1,pre_i]\times [i,nxt_i-1]\cup [pre_i+1,i]\times [nxt_i,nxtnxt_i-1] $$

于是我们定位到每个矩形即可。

考虑递归进行这个过程。如果我们知道 $[l,r]$ 内最大值下标为 $mx$，次大值下标为 $se$，不妨令 $mx<se$。

此时我们可以提取出矩形 $[l,mx]\times [se,r]$，往 $[l,se-1],[mx+1,r]$ 递归即可。

递归时进行记忆化，则每个矩形恰好被递归一次，总递归次数为 $2n$。

除第一次外区间的最大值下标可以在递归时传下去。第一次使用 $n$ 次询问查询即可。总次数为 $3n$。

code：

#include<bits/stdc++.h>
#define rep(i,j,k,...) for(int i=j;i<=k;i++)
using namespace std;

const int maxn=2070;

int a[maxn],n;
int ans[maxn][maxn];

int ask(int l,int r){
	cout<<"? "<<l<<" "<<r<<endl;
	int x;
	cin>>x;
	return x;
}

bool vis[maxn][maxn];

void solve(int l,int r,int mx){
	if(l==r) return;
	if(vis[l][r]) return;
	vis[l][r]=1;
	int se=ask(l,r),x,y;
	tie(x,y)=minmax(mx,se);
	rep(i,l,x) rep(j,y,r) ans[i][j]=se;
	solve(l,y-1,x),solve(x+1,r,y);
}

signed main(){
	cin>>n;
	int x=ask(1,n),l=x,r=x;
	while(r!=n&&ask(l,r+1)!=x) r++;
	while(l!=1&&ask(l-1,r)!=x) l--;
	int pos=(l==1? r+1: l-1);
	solve(1,n,pos);
	cout<<"!"<<endl;
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		cout<<ans[l][r]<<endl;
	}
}