P9291 [ROI 2018] Quick sort - 题解

· · 题解

神仙构造题。

依次考虑每个数 i \in [1, n]，尝试将值 i 操作到位置 i 上。由于单次操作是对奇偶项分组后合并为一个新的序列，故通过操作可以将一个位置到目标位置的距离减半。这样就可以产生一个 \Theta(n \log n) 的做法了：

// f[a[i]] = i
for(int i = 1; i <= n; i++) {
    while(a[i] != i) {
        // i 需放置在子区间的偶数位上
        if((f[i] - i) & 1) {
            apply(i, f[i]);
        } else {
            apply(i + 1, f[i]);
        }
    }
}

但是这种做法不够优秀，对本题而言需要近乎线性的解法。

延续这个思路并没有什么优秀做法，这个时候可以尝试一下转换视角。正难则反，如果这个问题是让我们通过逆操作，将排列 1 2 3 4 5... 操作成给定序列，是否有新的性质呢？

这也引出了本题最人类智慧的一步：运用转置原理，对逆排列通过逆操作进行排序，最后倒序输出操作序列。其中逆操作形如：选择一个子区间，将前半部分与后半部分取出，两部分交替加入结果序列。

这样一来，只要进行一步 (1, 2i) 的操作，就可以令 i 的位置倍增到 2i 处。当 2i > n 时，操作 (2i - n + 1, n) 可将 i 的位置移动到 n 上。

这样做好在哪里呢，这时 \text{highbit} 越大，代价反而越小了。形式化的讲，此时需要操作 \lfloor \log n \rfloor - \lfloor \log i \rfloor + 1 次（这里就认为 n 是 2 的幂次了）。对这个式子求和，如果你要忽略下取整符号，可以用斯特林公式 n! \approx \sqrt{2 \pi n} (\frac ne) ^ n 推导出一个粗略上界是 (1 + \log_2 e) n。当然也可以直接进行整数推导，可以证明操作次数上界在 2n 附近。最终结论就是，这样做的操作量是 \Theta(n) 的。

于是，考虑通过逆操作对原排列的逆排列排序，从 n 到 1 依次使每个数归位即可。结合一些随机扰动，可以进一步将操作次数卡进 6000。

个人认为这里逆操作的动机并不显然，但对这类构造题而言反向考虑的确是一个常见的套路，解构造题还是要善于转换视角。

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

constexpr int N = 3000 + 10;
int n, a[N], b[N], f[N];

inline void maintain() {
    for(int i = 1; i <= n; i++) {
        f[a[i]] = i;
    }
}
vector<pair<int, int>> seq;
inline void apply(int l, int r) {
    seq.emplace_back(l, r);
    int t = l; 
    for(int i = l + 1; i <= r; i += 2) {
        b[t++] = a[i];
    }
    for(int i = l; i <= r; i += 2) {
        b[t++] = a[i];
    }
    for(int i = l; i <= r; i++) {
        a[i] = b[i];
    }
    maintain();
}
inline void applyInv(int l, int r) {
    seq.emplace_back(l, r);
    int mid = (l + r - 1) >> 1, t = 0;
    for(int i = l, j = mid + 1; t < r - l + 1; t++) {
        if(t & 1) {
            b[t] = a[i++];
        } else {
            b[t] = a[j++];
        }
    }
    for(int i = l; i <= r; i++) {
        a[i] = b[i - l];
    }
    maintain();
}
inline void work(int l, int r) {
    while((l << 1) < r) {
        applyInv(1, l << 1);
        l <<= 1;
    }
    applyInv(2 * l - r + 1, r);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rec[N];

int main() {
    // freopen("sort.in", "r", stdin);
    // freopen("sort.out", "w", stdout);
    ios::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    maintain();
    for(int i = 1; i <= n; i++) {
        swap(f[i], a[i]);
        rec[i] = a[i];
    }
    maintain();

    do {
        seq.clear();
        for(int i = 1; i <= n; i++) {
            a[i] = rec[i];
        }
        maintain();

        int T = 10;
        while(T--) {
            int l = rng() % n + 1, r = rng() % n + 1;
            if(l > r) {
                swap(l, r);
            }
            if(l == r) {
                continue;
            }
            applyInv(l, r); 
        }
        for(int i = n; i >= 1; i--) {
            if(f[i] == i) {
                continue;
            }
            work(f[i], i);
        }
    } while(seq.size() >= 6000);

    reverse(seq.begin(), seq.end());
    cout << seq.size() << "\n";
    for(auto [l, r] : seq) {
        cout << l << " " << r << "\n";
    }
}