题解：P15652 [省选联考 2026] 排列游戏 / perm

· · 题解

考虑从小到大确定。

手玩一下发现可以这么构造：假设当前数 [0,i-1] 最左的位置在 l，最右的位置在 r，如果 \text{query}(l,r)>i，那么在 l,r 中的任意一个空位置放 i；否则 i 和原排列位置必须相同，先判断 i 在哪边，然后暴力把 l,r 往外扩展。只要扩展到第一个 \text{query}(l,r')>i 或者 \text{query}(l',r)>i 的位置。判断在哪边只要看 \text{query}(l,n-1)>i 还是 \text{query}(0,r)>i。特别地，0 的位置需要直接找出。直接实现，选短的那边判断，加上记忆化就是 1.5n+\log{n}。易证正确性。

现在有两个问题：找 0 需要 \log{n}，判断是哪边需要 1.5n。

对于 0，肯定要把找它的询问摊到后面的询问中。判断是哪边看起来没有办法去掉，那么想办法把判定的条件修改。以 i 在左边的情况为例，由于这是排列，i 肯定不在右边，把 [r+1,n-1] 加到询问的范围里不会影响查询的结果是否大于 i。那么就变成了查后缀，i 在右边同理变成了查前缀。

为了把查找 0 摊进来，我们从 0\sim n-1 遍历，查询后缀，一旦查到为 0，那么上一个位置就是 0。如果一直没查到就是 n-1。那么后续的每次后缀查询我们都查过了，就不用再查一遍。前缀的查询可以直接查。假设 0 的位置是 p，那么一共有 p+1+n-1-p=n 次查询，可以通过。用 set 维护空位置，时间 O(n\log{n})。

#include<iostream>
#include<vector>
#include<set>
#include<map>
#define PII pair<int,int>
#define mp make_pair
#include "perm.h"
using namespace std;
const int N=3e4+5;

void init(int c,int t){
    return;
}

map<PII,int> Map;

set<int> emp;

int ask(int l,int r){
    if(Map.count(mp(l,r))) return Map[mp(l,r)];
    return Map[mp(l,r)]=query(l,r);
}

vector<int> perm(int n){
    Map.clear(),emp.clear();
    Map[mp(0,n-1)]=n; 
    for(int i=0;i<n;i++) emp.insert(i);
    vector<int> ans;
    ans.resize(n);
    int nl,nr,p=-1;
    for(int i=0;i<n;i++){
        int res=ask(i,n-1);
        if(!res){
            p=i-1;
            break;
        }
    }
    if(p==-1) p=n-1;
    nl=nr=p,ans[p]=0;
    emp.erase(p);
    Map[mp(p,p)]=1;
    for(int i=1;i<n;i++){
        if(ask(nl,n-1)>i&&ask(0,nr)>i){
            auto it=emp.lower_bound(nl);
            ans[*it]=i;
            emp.erase(it);
        }
        else if(ask(nl,n-1)>i){
            for(int j=nr+1;j<n;j++){
                if(ask(0,j)>i){
                    ans[j]=i;
                    emp.erase(j);
                    nr=j;
                    break;
                }
            } 
        }
        else if(ask(0,nr)>i){
            for(int j=nl-1;j>=0;j--){
                if(ask(j,n-1)>i){
                    ans[j]=i;
                    emp.erase(j);
                    nl=j;
                    break;
                }
            }
        }
    }
    return ans;
}