CF-1073-E. Comparable Permutations（单调性的变化）

题目大意

1. 任务目标

已知一个隐藏的长度为 $n$ 的排列 $p$。你需要找到一个字典序最小的排列 $q$，使得 $q$ 满足以下两个条件：

• $q > p$ （$q$ 的字典序大于 $p$）

• $rev(q) > rev(p)$ （$q$ 翻转后的字典序大于 $p$ 翻转后的字典序）

注意： $q$ 必须是由 $p$ 中的元素重新排列得到的。你不需要直接输出 $q$，而是输出一个下标排列 $r$ ($1 \le r_i \le n$)，使得 $q_i = p_{r_i}$。如果不存在满足条件的 $q$，输出 $-1$。

2. 交互规则

• 你可以进行询问，格式为 ? i j，查询 $p_i < p_j$ 是否成立。

• 如果 $p_i < p_j$，交互库返回 $1$；否则返回 $0$。

• 每个测试点最多允许询问 $3n$ 次。

• 交互库是非自适应的（隐藏排列 $p$ 在交互开始前已确定）。

3. 样例解释

• 样例 1： $p = [5, 4, 2, 3, 1]$

  • 满足条件的最小 $q$ 为 $[5, 4, 3, 1, 2]$。
  • 验证：$q$ 比 $p$ 字典序大；$rev(q) = [2, 1, 3, 4, 5]$，$rev(p) = [1, 3, 2, 4, 5]$，显然 $rev(q) > rev(p)$。
  • 输出 $r = [1, 2, 4, 5, 3]$，因为 $p_1=5, p_2=4, p_4=3, p_5=1, p_3=2$。

• 样例 2： $p = [3, 1, 2, 4]$

  • 不存在同时满足 $q > p$ 且 $rev(q) > rev(p)$ 的排列 $q$，故输出 $-1$。

4. 数据范围

• $t \le 1000$，$n \le 2 \cdot 10^4$，所有测试用例的 $n$ 之和不超过 $2 \cdot 10^4$。

• 时间限制 2 秒，内存限制 256 MB。

思路讲解

一开始看这道题目，不能看出来像下面这张图的解法，但是我们会误以为这个情况的一些其他性质比较重要，但是最重要的是单调性的变化，因为没有单调性的变化意味着没有这个答案。

因此，这道题目关键点在于这个单调性的变化（即未发生单调性变化下操作是没有意义的，一定会违反题设条件），我们先来看这个情况，不难发现，在单调性变化之后执行交换与这个反转操作最好。

那么如果先下降呢？经过对拍验证以及这个推理，如果先下降再上升，是无法构造出答案的。原因：设在当前点，你需要构造 $q$，以满足题设条件。因此，你要提高 $q$ 的字典序，那么必须要在后面的点当中选一个比当前点高的（最优的是恰好高的），但是这样一来，就会导致 $\text{rev}(q)$ 的字典序下降（这个是无法挽救的，因为目前的更换的当前点处于上升序列，处于上升序列的其他点比当前点低，处于下降序列的其他点比当前点低），导致无法满足题设条件。

因此先下降，再上升的话，必须要再找一个下降。

然后，交换好以后，就想办法把这个上升序列插入到这个下降序列当中（有序插入，保持单调下降性），随便你用什么办法。

然后为了减少提问个数，我们使用了记忆化，就是问过的，就不再问了（注意问了 a b 的话，b a 也不要再问了）。

感觉这道题目难度主要还是在这个调试，代码和细节上。

AC代码

AC
https://codeforces.com/contest/2191/submission/359093232

源代码

/**
 * Problem: E. Comparable Permutations
 * Contest: Codeforces Round 1073 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2191/problem/E
 * Created: 2026-01-21 22:46:09
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */
#ifdef LOCAL
#include "E_grader.h"
Grader grader;
#endif

// 返回 1 为严格小于，返回 0 是 ≥
int query_is_a_lt_b(int a,int b,map<pair<int,int>,int> &memo) {
    if (a==b) return 1;
    if (memo.contains({a,b})) {
        return memo[{a,b}];
    }
    int res;
#ifdef LOCAL
    res = grader.query_is_a_lt_b(a,b);
#else
    cout<<"? "<<a<<" "<< b<<endl;
    cin>>res;
#endif
    memo[{a,b}]=res;
    memo[{b,a}]=res^1;
    return res;
}
int query_is_a_gt_b(int a,int b,map<pair<int,int>,int> &memo) {
    if (memo.contains({a,b})) {
        return !memo[{a,b}];
    }
    int res;
#ifdef LOCAL
    res=grader.query_is_a_lt_b(a,b);
#else
    cout<<"? "<<a<<" "<< b<<endl;
    cin>>res;
#endif
    memo[{a,b}]=res;
    memo[{b,a}]=res^1;
    return !res;
}
void out_ans(bool have_ans,const vector<ll> &perm,ll N) {
#ifdef LOCAL
    grader.out_ans(have_ans,perm,N);
    return;
#endif
    if (!have_ans) {
        cout<<"! "<<-1<<endl;
        return;
    }
    cout<<"! ";
    for (int i=1;i<=N;++i) {
        cout<<perm[i]<<" ";
    }
    cout<<endl;
}


void Solve() {
    ll N;
    cin >> N;
#ifdef LOCAL
    grader=Grader(N);
#endif

    map<pair<int,int>,int> memo;
    // 我们先来找一下最大的 i
    ll big_i=0;
    for (int i=N-1;i>=1;--i) {
        int is_a_small_b=query_is_a_lt_b(i,i+1,memo);
        if (is_a_small_b) {
            big_i=i;
            break;
        }
    }
    vector<ll> perm(N+2);
    for (int i=1;i<=N;++i) {
        perm[i]=i;
    }
    if (big_i==0) {
        out_ans(false,perm,N);
        return;
    }
    // 如果说 big_i 后有这个周旋的空间，那就很好了
    if (big_i!=N-1) {
        // 二分查找第一个比 i 大的 j
        ll j_1st_gt_i=0;
        // 6 5 4
        ll bsl=big_i+1,bsr=N;
        auto check=[&](ll idx) {
            int res=query_is_a_lt_b(big_i,idx,memo);
            return res;
        };
        while (bsl<bsr) {
            ll mid=(bsl+bsr+1)>>1;
            if (check(mid)) {
                bsl=mid;
            }else {
                bsr=mid-1;
            }
        }
        j_1st_gt_i=bsl;
        swap(perm[j_1st_gt_i],perm[big_i]);
        reverse(perm.begin()+big_i+1,perm.begin()+N+1);
        out_ans(true,perm,N);
    }else {
        // 我们要找到这个第二个下降出现（4 5 6这样子）
        ll end_of_down=big_i;
        ll sec_down_start=0;
        for (int i=big_i-1;i>=1;--i) {
            if (query_is_a_lt_b(i,i+1,memo)) {
                if (end_of_down-i>1) {
                    sec_down_start=i;
                    break;
                }
                end_of_down=i;
            }
        }
        if (sec_down_start==0) {
            // 不开始第二次下降等于不对
            out_ans(false,perm,N);
            return;
        }
        auto check_bs=[&](ll i) {
            return query_is_a_gt_b(i,sec_down_start,memo);
        };
        auto range1=views::iota(sec_down_start+1,end_of_down);
        auto it1=ranges::partition_point(range1,check_bs);
        auto range2=views::iota(end_of_down,N+1)|views::reverse;
        auto it2=ranges::partition_point(range2,check_bs);

        it1=ranges::prev(it1);

        ll to_be_select=*it1;
        if (it2!=range2.begin()) {
            it2=ranges::prev(it2);
            if (query_is_a_lt_b(*it2,*it1,memo)) {
                to_be_select=*it2;
            }
        }
        swap(perm[to_be_select],perm[sec_down_start]);
        vector after_sec_down_ls(perm.begin()+end_of_down,perm.begin()+N+1);
        ll idx=-1;
        auto check=[&](ll pos) {
            if (idx==-1) {
                if (query_is_a_lt_b(pos,after_sec_down_ls[idx+1],memo)) {
                    return true;
                }
                return false;
            }
            if (idx>=after_sec_down_ls.size()) {
                --idx;
                return true;
            }
            if (idx+1>=after_sec_down_ls.size()) {
                if (query_is_a_lt_b(after_sec_down_ls[idx],pos,memo)) {
                    return true;
                }
                return false;
            }
            if (query_is_a_lt_b(after_sec_down_ls[idx],pos,memo) &&
                query_is_a_lt_b(pos,after_sec_down_ls[idx+1],memo)) {
                return true;
            }
            return false;
        };

        for (int i=end_of_down-1;i>sec_down_start;--i) {
             ll pos=perm[i];
            while (!check(pos)) {
                ++idx;
            }
            after_sec_down_ls.insert(after_sec_down_ls.begin()+idx+1,pos);
        }
        for (int i=sec_down_start+1;i<=N;++i) {
            perm[i]=after_sec_down_ls[i-sec_down_start-1];
        }
        out_ans(true,perm,N);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while(lT--)
        Solve();
    return 0;
}

/*
1



_______________[ Stress test, testcase 3 INPUT ]_______________
1
5
2 3 5 1 4

_______________[ Stress test, testcase 3 OUTPUT]_______________
WA
hide perm: 2 3 5 1 4
ans_ls: 2 4 1 3 5
ans_rec: 2 3 5 4 1


WA
hide perm: 8 1 9 3 5 4 2 6 7
ans_ls: 8 1 9 4 2 3 5 6 7
ans_rec: 8 1 9 4 6 7 2 3 5

WA
hide perm: 2 3 1 4 5
ans_ls: 3 1 2 4 5
ans_rec: 3 4 5 1 2

*/

暴力 grader.h 实现（函数式交互）

//
// Created by zz y on 2026/1/20.
//

#ifndef E_GRADER_H
#define E_GRADER_H
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Grader {
    vector<ll> perm_ls;
    ll N;
    // vector<ll> num_pos_ls;
    vector<ll> ans_ls;
    ll cnt_query=0;
    bool is_a_gt_b(const vector<ll> &a,const vector<ll> &b) const {
        for (int i=1;i<=N;++i) {
            if (a[i]<b[i]) {
                return false;
            }else if (a[i]>b[i]) {
                return true;
            }
        }
        return false;
    }

    bool check() {
        vector<ll> ans_ls_rev=ans_ls;
        vector<ll> perm_ls_rev=perm_ls;
        reverse(perm_ls_rev.begin()+1,perm_ls_rev.begin()+N+1);
        reverse(ans_ls_rev.begin()+1,ans_ls_rev.begin()+N+1);
        return is_a_gt_b(ans_ls,perm_ls) && is_a_gt_b(ans_ls_rev,perm_ls_rev);
    }
    bool exist_ans=false;
    explicit Grader(ll N):N(N) {
        perm_ls.resize(N+2);
        for (int i=1;i<=N;++i) {
            cin>>perm_ls[i];
        }
        // shuffle(perm_ls.begin()+1,perm_ls.begin()+N+1,rng);
        // for (int i=1;i<=N;++i) {
        //     ll num=perm_ls[i];
        //     num_pos_ls[num]=i;
        // }
        ans_ls=perm_ls;
        sort(ans_ls.begin()+1,ans_ls.begin()+N+1);
        do {
            if (check()) {
                exist_ans=true;
                break;
            }
        }while (next_permutation(ans_ls.begin()+1,ans_ls.begin()+N+1));
    }
    Grader()=default;
    int query_is_a_lt_b(int a,int b) {
        // if (a==b) return 1;
        if (a<=0 || a>N || b<=0 || b>N) {
            cout<<"a b over [1,N] "<< a << " "<< b<<"\n";
        }
        ++cnt_query;
        if (cnt_query>3*N) {
            cout<<"over 3*N queries"<<"\n";
        }
        return perm_ls[a]<perm_ls[b];
    }

    void out_ans(bool have_ans,const vector<ll> &perm,ll N) {
        vector<ll> ans_rec(N+2);
        for (int i=1;i<=N;++i) {
            ans_rec[i]=perm_ls[perm[i]];
        }
        auto print_error=[&]() {
            cout<<"WA\n";
            cout<<"exist_ans: "<<exist_ans<<"\n";
            cout<<"hide perm: ";
            for (int j=1;j<=N;++j) {
                cout<<perm_ls[j]<<" ";
            }
            cout<<"\n";
            cout<<"ans_ls: ";
            for (int j=1;j<=N;++j) {
                cout<<ans_ls[j]<<" ";
            }
            cout<<"\n";
            cout<<"ans_rec: ";
            for (int j=1;j<=N;++j) {
                cout<<ans_rec[j]<<" ";
            }
            cout<<"\n";
        };
        if (exist_ans!=have_ans) {
            print_error();
            return;
        }
        if (!exist_ans && exist_ans==have_ans) {
            cout<<"AC\n";
            return;
        }

        for (int i=1;i<=N;++i) {
            if (ans_rec[i]!=ans_ls[i]) {
                print_error();
                return;
            }
        }
        cout<<"AC\n";
    }
};


#endif //E_GRADER_H

心路历程（WA，TLE，MLE……）