CF-1073-E. Comparable Permutations（单调性的变化） · znzryb
## 题目大意
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](https://codeforces.com/contest/2191/submission/359093232)
::: 源代码
```cpp
/**
* 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 实现（函数式交互）
```cpp
//
// 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……）