[EC Final 2022] Inversion

形式化题目

有一个隐藏的排列 $p_1,p_2,\dots,p_n$ ，你只能通过询问获取信息：每次给出 $1\leqslant l\leqslant r\leqslant n$ ，对方回答

\left(\sum_{l\leqslant i<j\leqslant r}[p_i>p_j]\right)\bmod 2,

也就是区间 $p_l,\dots,p_r$ 内逆序对个数的奇偶性。询问次数不能超过 $4\times10^4$ ，最后要输出整个排列 $p_1,\dots,p_n$ 。

暴力解法

思路

最直接的做法是逐个位置硬算大小关系。

第一步，先把「任意区间内逆序对个数的奇偶性」全部搞到手。记

\mathrm{inv}(l,r)=\left(\sum_{l\leqslant i<j\leqslant r}[p_i>p_j]\right)\bmod 2 .

固定 $r$ 并让 $l$ 从 $r-1$ 递减，用变量 $\mathrm{cnt}$ 维护 $[l,r-1]$ 中比 $p_r$ 大的元素个数，就有递推

\mathrm{inv}(l,r)=\mathrm{inv}(l,r-1)\oplus(\mathrm{cnt}\bmod 2).

第二步， $p_i$ 恰好等于「比它大的元素个数」再加 $1$ ，于是只要得到两两大小关系就够了：

p_i=n-\#\{j: p_j>p_i\}+1 .

那么怎么用区间逆序对去问出两个单点的大小关系？关键恒等式是

[p_l>p_r]=\mathrm{inv}(l,r)\oplus\mathrm{inv}(l+1,r)\oplus\mathrm{inv}(l,r-1)\oplus\mathrm{inv}(l+1,r-1),

其中约定 $l\geqslant r$ 时 $\mathrm{inv}(l,r)=0$ 。把 $[l,r]$ 内的逆序对按「是否用到 $p_l$ 」「是否用到 $p_r$ 」分成四类，前三类分别是 $\mathrm{inv}(l+1,r)$ 、 $\mathrm{inv}(l,r-1)$ 、 $\mathrm{inv}(l+1,r-1)$ ，而第四类被异或了三次（每次都要用到 $p_l,p_r$ ，其贡献被算 $3$ 次后剩下 $1$ 次），加上 $p_l>p_r$ 本身的贡献正好拼成 $\mathrm{inv}(l,r)$ 。

所以暴力就是：对所有 $\binom{n}{2}$ 个位置对都按上面的式子判断一次大小关系，累加出每个位置的名次。做法绝对正确，但代价是 $\Theta(n^2)$ 次询问， $n=2000$ 时约 $2\times10^6$ 次，超限 $50$ 倍。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:30
 */
// brute.cpp：暴力对拍解。
//
// 思路（把每个位置和其余所有位置都比一遍）：
//   1. 先按定义求出所有 inv(l,r)，也就是交互器对所有可能询问的回答；
//   2. 再用同一个恒等式
//        [p_l > p_r] = inv(l,r) ^ inv(l+1,r) ^ inv(l,r-1) ^ inv(l+1,r-1)
//      得到每一对位置的大小关系；
//   3. p_i 就是比它大的元素个数 bigger[i]，故 p_i = n - bigger[i]。
//
// 正确但很慢：一共要处理 Θ(n^2) 对位置，换算成真实的询问次数也是 Θ(n^2)，
// 在 n=2000 时达到 10^6 级别，远超题目的 4*10^4 次上限。
// 本地对拍时输入是 “n + 隐藏排列”，排列只用来扮演交互器。
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2005;

int n;
static unsigned char invtab[maxn][maxn]; // invtab[l][r] = p_l..p_r 内逆序对个数的奇偶性
static int perm_in[maxn];
int bigger[maxn];                        // bigger[i] = 比 p_i 大的元素个数

// 按定义算出所有区间的逆序对奇偶性：固定 r，l 递减，cnt 维护 [l, r-1] 中比 p_r 大的个数。
void build_inv_table() {
    for (int r = 1; r <= n; r++) {
        int cnt = 0;
        for (int l = r - 1; l >= 1; l--) {
            if (perm_in[l] > perm_in[r]) {
                cnt++;
            }
            invtab[l][r] = (unsigned char)(invtab[l][r - 1] ^ (cnt & 1));
        }
    }
}

void solve() {
    // 一次“询问”：直接查预先算好的表。
    for (int l = 1; l <= n; l++) {
        for (int r = l + 1; r <= n; r++) {
            // 用恒等式还原大小关系，inv 中越界的部分按 0 处理。
            int cmp = invtab[l][r] ^ invtab[l + 1][r] ^ invtab[l][r - 1] ^ invtab[l + 1][r - 1];
            if (cmp) {
                bigger[r]++; // p_l > p_r
            } else {
                bigger[l]++; // p_r > p_l
            }
        }
    }

    cout << "!";
    for (int i = 1; i <= n; i++) {
        cout << " " << n - bigger[i];
    }
    cout << endl;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> perm_in[i];
    }
    build_inv_table();
    solve();

    return 0;
}

复杂度

时间复杂度 $O(n^2)$ （本地对拍时还要 $O(n^2)$ 打交互器答案表），询问次数 $\Theta(n^2)$ 。

瓶颈

询问次数是 $\Theta(n^2)$ 量级，远远超过 $4\times10^4$ 。而信息量其实足够：每次询问给出 $1$ bit， $4\times10^4$ 个 bit 早已超过还原 $2000!$ 种排列所需。问题不在于信息不够，而在于暴力没有复用已经获得的信息。

正解

思路

突破口在于：我们真正需要的是「每个元素在已确定前缀里排第几」，而这件事天然适合插入排序 + 二分。

第一步：把「比大小」的代价压到 2 次询问。

沿用前面推出的恒等式

[p_l>p_r]=\mathrm{inv}(l,r)\oplus\mathrm{inv}(l+1,r)\oplus\mathrm{inv}(l,r-1)\oplus\mathrm{inv}(l+1,r-1).

如果每比较一次都要现查 4 个值，代价就太高了。注意到插入排序是逐个处理位置的：处理到 $i$ 时，前面 $i-1$ 个位置已经排好。记

E[l]=\mathrm{inv}(l,i-1),

即「从位置 $l$ 到当前已插入前缀末尾」的逆序对奇偶性。那么恒等式中的后两项就变成了 $E[l]$ 与 $E[l+1]$ ，只剩下 $\mathrm{inv}(l,i)$ 和 $\mathrm{inv}(l+1,i)$ 需要现问：

[p_l>p_i]=\mathrm{inv}(l,i)\oplus\mathrm{inv}(l+1,i)\oplus E[l]\oplus E[l+1].

这里每次比较用掉 2 次询问；当 $l+1=i$ 时 $\mathrm{inv}(l+1,i)=\mathrm{inv}(i,i)=0$ 不必询问，只用 1 次。这正是全部代价的来源。

第二步：二分找名次。

插入 $p_i$ 时，维护一张有序表 $elem\_at[0..i-2]$ ，其中 $elem\_at[t]$ 是当前前缀里名次为 $t$ （ $0$ 起始）的元素下标。要确定 $p_i$ 的名次，就是找最小的 $r$ 使 $p_{elem\_at[r]}>p_i$ 。数组本身有序，可以直接二分：

text

1
2
3
4
5
6lo = 0, hi = i-1
while lo < hi:
    mid = (lo+hi)/2, j = elem_at[mid]
    if p_j > p_i:  hi = mid
    else:          lo = mid+1
r = lo

每轮迭代恰好比较一次，比较代价由第一步的公式给出，稳定在 1~2 次询问。

第三步：用名次增量更新 $E$ ，不花一次询问。

定位出名次 $r$ 之后，我们可以顺手算出每个 $l<i$ 的 $[p_l>p_i]$ ：因为 $E$ 里比较的全是同一个前缀内的名次，而名次是前缀内的相对大小，所以

p_l>p_i \iff rank[l]\geqslant r .

于是从 $l=i-1$ 递减扫到 $1$ ，用变量 $g$ 累积「 $[l,i-1]$ 中比 $p_i$ 大的元素个数」的奇偶性：

g\mathrel{\oplus}=[rank[l]\geqslant r],\qquad E[l]\mathrel{\oplus}=g .

这一步只动数组、不发询问。最后把 $i$ 在有序表里的名次 $r$ 落实：名次 $\geqslant r$ 的元素整体后移一位，并令 $rank[i]=r$ 、 $E[i]=0$ （ $\mathrm{inv}(i,i)=0$ ）。

循环 $n$ 轮之后， $rank[i]+1$ 就是 $p_i$ ，直接按位置输出即可。

询问次数为什么够用

插入 $p_i$ 时二分区间长度为 $i-1$ ，最坏迭代 $\lceil\log_2 i\rceil$ 次，每次 2 次询问，所以总询问次数不超过

2\sum_{i=1}^{n}\lceil\log_2 i\rceil = 2\times 19953 = 39906 < 40000 \quad (n=2000).

题面上限偏偏卡在 $4\times10^4$ 而不是 $2^k$ 之类的整数，正是为了逼出这个 $2$ 倍常数：只要一次比较花 3 次询问（ $\approx 59859$ ）或比较次数再多一点就会被卡掉。另外注意 $p_1$ 不需要比较， $i=1$ 那一项贡献为 0。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-02 15:23
 * update_at: 2026-10-03 12:30
 */
// P9721 [EC Final 2022] Inversion —— 交互题
//
// 询问 ? l r 返回 p_l..p_r 中逆序对个数的奇偶性，要求在 4*10^4 次询问内还原排列。
//
// 核心恒等式：记 inv(l,r) 为 p_l..p_r 内逆序对个数的奇偶性（约定 l>=r 时 inv=0），
// 对 l<r 有
//     [p_l > p_r] = inv(l,r) ^ inv(l+1,r) ^ inv(l,r-1) ^ inv(l+1,r-1)
// 把 [l,r] 中的逆序对按“是否用到 p_l”“是否用到 p_r”分成四类即可得到这个式子，
// 于是任意两个位置的大小关系只需要 4 次询问（相邻的 inv 还能复用）。
//
// 做法：插入排序 + 二分查找。
//   依次把 p_1,p_2,...,p_n 插入一张有序表，保持当前前缀的相对大小关系。
//   插入 p_i 时二分定位它的名次，每次比较用上面的恒等式（j+1==i 时只需 1 次询问）。
//   同时维护 E[l] = inv(l, i-1)，即当前前缀中从位置 l 到末尾的逆序对奇偶。
//   定位出名次 r 之后，p_l > p_i 等价于 rank[l] >= r（名次都在同一前缀内比较），
//   所以可以在 O(n) 次“不花询问”的数组更新里把 E 从 inv(.,i-1) 推进到 inv(.,i)。
//   询问次数上界为 2 * sum_{i=1}^{n} ceil(log2 i) = 39906 <= 4*10^4。
//
// 本地对拍说明：真实评测只给 n，排列是隐藏的。verify.sh 会把
// “n 加上整个排列”一起重定向进来，程序检测到 stdin 是普通文件时进入本地模式，
// 自己按定义把交互器的答案预计算好，这样同一份代码既能交互提交也能本地对拍。
#include <bits/stdc++.h>
#include <poll.h>
#include <sys/stat.h>
using namespace std;

const int maxn = 2005;

int n;
bool local_mode = false;          // 是否处于本地对拍模式
long long ask_count = 0;          // 已经发出的询问次数
static unsigned char invtab[maxn][maxn]; // 本地模式下预先算好的交互器答案
static int perm_in[maxn];         // 本地模式下读入的隐藏排列

int rank_of[maxn];                // rank_of[x] = p_x 在当前前缀中的名次（从 0 开始）
int elem_at[maxn];                // elem_at[t] = 当前前缀中名次为 t 的元素下标
unsigned char E[maxn];            // E[l] = inv(l, 当前前缀末尾) 的奇偶

// 向交互器询问 [l,r] 内逆序对个数的奇偶性；l>=r 时答案必为 0，不必询问。
int ask(int l, int r) {
    if (l >= r) {
        return 0;
    }
    ask_count++; // 只有真正会发出去的询问才计数（两个模式下都不发 l>=r 的询问）
    if (local_mode) {
        return invtab[l][r];
    }
    cout << "? " << l << " " << r << endl; // endl 会刷新输出
    int ans;
    cin >> ans;
    return ans;
}

// 本地模式：直接按定义算出所有 inv(l,r) 的奇偶性，充当交互器。
// 固定 r，令 l 从 r-1 递减，用 cnt 维护 [l, r-1] 中比 p_r 大的元素个数。
void build_local_table() {
    for (int r = 1; r <= n; r++) {
        int cnt = 0;
        for (int l = r - 1; l >= 1; l--) {
            if (perm_in[l] > perm_in[r]) {
                cnt++;
            }
            invtab[l][r] = (unsigned char)(invtab[l][r - 1] ^ (cnt & 1));
        }
    }
}

// 判断是否应该在本地模式下运行：
// 数据被重定向自普通文件（verify.sh 的 “< in” 就是这种），或者管道里还留着后续数据。
bool detect_local_mode() {
    struct stat st;
    if (fstat(0, &st) == 0 && S_ISREG(st.st_mode)) {
        return true;
    }
#if defined(__unix__) || defined(__APPLE__)
    struct pollfd pfd;
    pfd.fd = 0;
    pfd.events = POLLIN;
    pfd.revents = 0;
    if (poll(&pfd, 1, 0) > 0 && (pfd.revents & POLLIN)) {
        return true;
    }
#endif
    // cin 自己的缓冲区里可能已经缓存了未消费的数据（非空白才算）。
    if (cin.rdbuf()->in_avail() > 0) {
        int c = cin.rdbuf()->sgetc();
        if (!isspace((unsigned char)c)) {
            return true;
        }
    }
    return false;
}

void read_data() {
    cin >> n;
    local_mode = detect_local_mode();
    if (local_mode) {
        for (int i = 1; i <= n; i++) {
            cin >> perm_in[i];
        }
        build_local_table();
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        // 二分查找 p_i 的名次 r：最小的 r 使 elem_at[r] 对应的数比 p_i 大。
        // 名次的取值范围是 [0, i-1]（当前前缀共有 i-1 个元素）。
        int lo = 0, hi = i - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            int j = elem_at[mid];
            int gt = ask(j, i) ^ ask(j + 1, i) ^ E[j] ^ E[j + 1];
            if (gt) {
                hi = mid;      // p_j > p_i，插入点不会在 mid 之后
            } else {
                lo = mid + 1;  // p_j < p_i，插入点至少在 mid+1
            }
        }
        int r = lo;

        // 更新 E：g 表示 [l, i-1] 中比 p_i 大的元素个数（mod 2）；
        // p_l > p_i <=> rank_of[l] >= r，所以不需要额外询问。
        int g = 0;
        for (int l = i - 1; l >= 1; l--) {
            if (rank_of[l] >= r) {
                g ^= 1;
            }
            E[l] ^= g;
        }
        E[i] = 0; // inv(i,i) = 0

        // 名次 >= r 的元素整体后移一位，再把 i 放到名次 r 上。
        for (int t = i - 2; t >= r; t--) {
            int j = elem_at[t];
            rank_of[j] = t + 1;
            elem_at[t + 1] = j;
        }
        elem_at[r] = i;
        rank_of[i] = r;
    }

    // 名次从 0 开始，所以 p_i = rank_of[i] + 1，直接按位置 1..n 输出。
    cout << "!";
    for (int i = 1; i <= n; i++) {
        cout << " " << rank_of[i] + 1;
    }
    cout << endl;

    if (local_mode) {
        fprintf(stderr, "# 本地模式：共模拟询问 %lld 次（上限 40000）\n", ask_count);
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    read_data();
    solve();
    return 0;
}

复杂度

时间复杂度 $O(n^2)$ （每轮插入的 $E$ 更新与有序表后移各是 $O(n)$ ，只有 $\log$ 次真的发询问），空间 $O(n)$ 辅助数组加 $O(n^2)$ 的本地对拍表；真实交互时询问次数 $\leqslant 39906$ 。

总结

核心恒等式： $[p_l>p_r]=\mathrm{inv}(l,r)\oplus\mathrm{inv}(l+1,r)\oplus\mathrm{inv}(l,r-1)\oplus\mathrm{inv}(l+1,r-1)$ ，把「单点比较」化成「区间逆序对奇偶性」的四项异或。
降常数：按位置顺序插入、维护 $E[l]=\mathrm{inv}(l,i-1)$ ，把恒等式中的两项变成已知，单次比较只要 2 次询问（ $l=i-1$ 时 1 次）。
二分 + 增量更新：在有序表里二分定名次，再用 $p_l>p_i \iff rank[l]\geqslant r$ 在 $O(n)$ 次数组操作内把 $E$ 从 $i-1$ 推进到 $i$ ，不额外消耗询问。
复杂度记账： $2\sum_{i=1}^{n}\lceil\log_2 i\rceil=39906$ ，刚好卡在 $4\times10^4$ 上限之内——上限的数字本身就是「插入排序二分 + 2 次询问」这个做法的签名。