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

· · 题解

挑战最短代码。

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

例如，当 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;
    }
}