题解：P9291 [ROI 2018] Quick sort

· · 题解

这是一个并不正经的乱搞做法。

考虑 O(n\log n) 怎么做。设 p_x 表示 x 这个数在排列中的位置。从大到小依次让每个数归位，当我们要让 x 这个数归位时，只要 p_x\not=x 就一直操作 [p_x,x] 这个区间，这样每次都能让 x-p_x 减半，总次数就是 O(n\log n)。需要大约 30000 次操作，无法通过。

注意到一次操作的左端点并不一定需要是 p_x，只要和 p_x 的奇偶性相同就好了。考虑找到一个最小的 y，使得 p_y,p_{y+1},\dots,p_x 的奇偶性全都相同，然后操作 [\min_{i=y}^xp_i,x] 这个区间。这样的一次操作可以让 [y,x] 内的所有数到其位置的距离都减半。

容易证明，在随机数据下，这个做法可以让总次数期望乘 \frac{1}{2}，于是可以通过。

::::info[代码]

#include<bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const int maxn = 3005;
int n;
int a[maxn], p[maxn];
vector<pii> ans;
void qsort(int l, int r) {
    ans.push_back(mkp(l, r));
    vector<int> tmp;
    for (int i = l + 1; i <= r; i += 2) tmp.push_back(a[i]);
    for (int i = l; i <= r; i += 2) tmp.push_back(a[i]);
    for (int i = l; i <= r; i++) p[a[i] = tmp[i - l]] = i;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], p[a[i]] = i;
    for (int i = n; i >= 1; i--)
        while (p[i] != i) {
            int x = i, y = p[i];
            while (x > 1 && p[x - 1] % 2 == p[i] % 2) y = min(y, p[--x]);
            qsort(y, i);
        }
    cout << ans.size() << '\n';
    for (auto x : ans) cout << x.fi << ' ' << x.se << '\n';
    return 0;
}

::::