题解：P15502 [ICPC 2025 APC] Book Sorting

· · 题解

P15502 [ICPC 2025 APC] Book Sorting 题解

好题！来一发不一样的题解。

题目大意

给定一个排列，你有三种操作，最后要求其变成递增序列（a_i=i）：

  1. 交换相邻两项
  2. 将某一项放最前面
  3. 将某一项放最后面

求最少操作数。

题目解法

结论 1： 操作二一定只对值为 1, 2, \cdots, l 的数（即值域前缀）操作，操作三一定只对值为 r, r+1, \cdots, n 的数操作。

证明： 只考虑操作二，操作三同理。设 S 为被进行过操作二的数的集合，l 为被进行过操作二中的数的最大值（l=\max S）。

那么假如有一个数 x 小于 l 并且没有被进行操作二，那当 l 被放到第一个之后，必然会和 x 进行一次交换操作（操作 1）。

因此，1 到 l 中的数至少会进行 l 次操作，原因如下：

但是，这样是不优的，因为我们可以直接对 l, l-1, \cdots, 1 依次使用操作二，这样就能直接让它们排好序，并且刚好使用 l 次操作。

因此，我们可以不妨假设操作二一定对值为 1, 2, \cdots, l 的数操作，操作三一定对值为 r, r+1, \cdots, n 的数操作。

定义 1： 设 f(l, r) 表示在原序列中只考虑值域在 [l, r] 之间的数时的逆序对数。

举个例子，假设原序列为 4, 5, 2, 3, 1，那么 f(2, 4)=2，因为只保留 [l, r] 之间的数时序列变为 4, 2, 3，其逆序对数是 2。

特别地，当 l>r 时，定义 f(l, r)=0。

结论 2： 由结论 1，可设没被操作二和三操作的数为 [L, R] 中的每个数，那么答案就是 \min\limits_{1 \le l < r \le n} l + (n+1-r) + f(l+1, r-1)。

证明： l + (n+1-r) 是操作二和三的总个数，接下来只需考虑值域在 [l+1, r-1] 内的数。而交换相邻两项最多让逆序对数 -1，因此最少需要逆序对数次操作。这个次数是很显然可以达到的。

于是乎，我们得到了一个似乎是 O(n^4) 的做法？不过注意值域区间逆序对可以用莫队优化，这里可以轻松优化到 O(n^2)（后面会再讲）。

定义 2： 设 g(l, r)=l + (n+1-r) + f(l+1, r-1)。

结论 3： g 满足四边形不等式。

证明： 即 l \le L \le R \le r 时 g(l, R)+g(L, r) \le g(l, r) + g(L, R)。

因为有关 l 和 n+1-r 的几项显然消掉了，只需证明 f 满足四边形不等式。

而这是显然的，因为 RHS 比 LHS 少了 [l, L) 与 (R, r] 之间的逆序对数贡献，手推一下并不难理解。

定义 3： 令右端点 r 为常数，设 l=opt(r) 为 g(l, r) 取到最小值时的最小的 l。

结论 4： opt(r) 关于 r 单调不减。

这是四边形不等式的经典结论，即决策单调性。略证一下：

使用反证法，假设 l_1=opt(r)>opt(r+1)=l_2。那么：

两式相加即和四边形不等式矛盾。

于是，我们可以使用决策单调性优化。那么，我们只需要快速求出 f(l, r) 的值。考虑莫队。

简单口糊一下，自己想可能更容易明白。用树状数组维护原数组每个位置对应的数的值在不在区间 [l, r] 中。每扩充右端点，即加入一个 r 时，只需查询在 r 所在位置右侧的数的数量，并更新 r 所在位置的树状数组。扩充左端点，删除左右端点同理。

复杂度

最终复杂度 O(n \log^2 n)。决策单调性一个 \log，树状数组一个 \log。

注意这里并不是普通的莫队的 O(\sqrt{n}) 复杂度，因为外面套了个决策单调性优化，具体证明详见 OI-wiki，可在此页面中搜索“非随机访问的复杂度证明”。

AC 代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define int long long
#define inf 1e9
#define lb(w) (w & -w)
#define debug(x) cerr << #x << ": " << x << endl
using namespace std;

const int MAXN = 1e6 + 7;
int a[MAXN], pos[MAXN], tree[MAXN], n;

void add(int idx, int val) { for (; idx <= n; idx += lb(idx)) tree[idx] += val; }
int query(int idx) { int cnt = 0; for (; idx; idx -= lb(idx)) cnt += tree[idx]; return cnt; }

struct MO
{
    int l = 1, r = 0, ans;
    void addR() {
        ans += query(n) - query(pos[++r]);
        add(pos[r], 1);
    }
    void addL() {
        ans += query(pos[--l]);
        add(pos[l], 1);
    }
    void delR() {
        add(pos[r], -1);
        ans -= query(n) - query(pos[r--]);
    }
    void delL() {
        add(pos[l], -1);
        ans -= query(pos[l++]);
    }
    int calc(int L, int R) {
        while (r < R) addR();
        while (l > L) addL();
        while (r > R) delR();
        while (l < L) delL();
        return ans;
    }
} mo;

int ANS = inf;

int f(int l, int r) {
    if (l == r + 1) return n;
    if (l > r) return inf;
    return (l - 1) + (n - r) + mo.calc(l, r);
}

void solve(int l, int r, int optl, int optr) {
    if (l > r) return;
    int mid = l + r >> 1, optm = optl, ans = inf;
    for (int i = optl; i <= optr; i++) {
        int F = f(i, mid);
        if (F < ans) ans = F, optm = i;
    }
    ANS = min(ANS, ans);
    solve(l, mid - 1, optl, optm);
    solve(mid + 1, r, optm, optr);
}

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i;
    solve(1, n, 1, n);
    cout << ANS << '\n';
}