题解：P12446 [COTS 2025] 答好位 / Vrsta

挑战最短代码。

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

例如，当

a=[2,8,1,5,9,6,3,7,4]

时，我们可以打出以下表：（第

i

行第

j

列表示区间

[i,j]

的次大值下标，若不存在则为

0

）。

CPP

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：

CPP

#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;
	}
}

题解：P12446 [COTS 2025] 答好位 / Vrsta

文章操作

相关推荐

评论

题解：P12446 [COTS 2025] 答好位 / Vrsta