题解：P16362 [BalticOI 2026] Sort

Sonetto37 · 2026-07-26 22:29:09 · 题解

题目说将 [1, a] 或者 [n-b+1, n] 进行排序，使得操作多次后，变成一个有序的东西，问操作最小值。

首先需要考虑的是，如何排序，使得 [1, a] 和 [n-b+1, n] 的操作排序是最优的。

很容易可以想到，第一关键字是值的大小，第二关键字是下标的大小。

考虑 a < n - b + 1 的情况，此时两个点不具有交集。

那么一定需要保证 [1, a] 中的元素，在 [1, n] 排序后 [1, a] 的元素相同。那么 [n-b+1, n] 的要求也是这样的。还有一个条件就是 [a+1, n-b] 中的元素是有序的。这个时候答案只可能在 [-1, 2] 中。因为要么是不合法，要么就是 [1, a] 或 [n-b+1, n] 产生的贡献。

然后考虑 a \ge n - b + 1 的情况，此时两个点具有交集，说明 [a+1, n-b] 中可以交换元素。

有 3 种情况需要考虑，最初最优，过程最优，结束最优。

我们发现过程最优就是两个操作交替着来，那么结束最优就只能是那么有序了。

对于最初最优，因为只有两种情况，我们可以直接枚举得到答案。

不妨考虑将答案为 0 或 1 的情况讨论出来。

当只用排零次时，很明显，就是需要保证 [1, n] 有序。

只用排一次就是排一次 [1, a] 或 [n-b+1, n]，当我们执行 [1, a] 排序时，一定需要保证 [a+1, n] 中的元素有序且在 [1, n] 排序后的元素相同，同理可得执行 [n-b+1,n] 排序的要求。

其他情况就是操作大于 2 的时候了。

考虑把图画出来。

我们定义 x_1 为原来在 [1, a] 中，但排序后应该在 [a+1,n] 中的元素个数；x_2 为原来在 [n-b+1,a] 中，但排序应该在 [a+1, n] 中的元素个数。

然后定义 y_1 为原来在 [n-b+1, n] 中，但排序后应该在 [1,n-b] 中的元素个数；y_2 为原来在 [n-b+1, a] 中，但是排序应该在 [1, n-b] 中的元素个数。

考虑第一次排序的是区间 [n-b+1, n]。那么 x_2 的元素也就在 [a+1, n] 中了。那么对于 [1, a] 中需要交换的元素也就变成了 x_1-x_2 了，那么需要交换的次数为 1+\frac{x_1-x_2}{a-n+b}，这个 1 是因为第 2 轮才开始进行。但是因为是轮换，所以还需要乘 2，所以次数是 1 + 2\frac{x_1-x_2}{a-n+b}。同时， 从 [n-b+1, n] 中需要到 [1, a] 的元素执行轮数就是 2\frac{y_1}{a-n+b}，最终答案就是就是 \max(2, \max(1 + 2\frac{x_1-x_2}{a-n+b}, 2\frac{y_1}{a-n+b}))。

同理可得第一次排序的区间是 [1, a] 的情况了。

最终答案就是：

可能会有些问题？

为什么要与 2 进行比较？

可能出现一次就将所有元素归回排序后的区间的情况，但是存在区间不是有序的，所以需要和 2 取最大值。

有一组样例，可以手模一下。

4 1
2 1 4 3
3 2

那这样不是错的吗？

当然不是错的呀，因为这是排序，不会存在无序的情况。

然后就做完了。

代码如下：

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

const int N = 2e5+10;
const int inf = 0x3f3f3f3f3f3f3f3f;

struct node {
    int x, id;
} b[N];

int n, Q;
int a[N];

int p[N];

int f[N];
int pre[N], suf[N];

inline int Ceil(int a, int b) {
    return (a + b - 1) / b;
}

bool cmp(node x, node y) {
    if (x.x != y.x) return x.x < y.x;
    return x.id < y.id;
}

int nowpos;
int ver[N];
int ls[N*30], rs[N*30], sum[N*30];

void copy(int a, int b) {
    ls[a] = ls[b], rs[a] = rs[b];
    sum[a] = sum[b];
}

int doBuild(int k, int l, int r) {
    nowpos = max(nowpos, k);
    if (l == r) {
        return k;
    }
    int mid = (l + r) >> 1;
    ls[k] = doBuild(k*2, l, mid);
    rs[k] = doBuild(k*2+1, mid+1, r);
    sum[k] = sum[k*2] + sum[k*2+1]; 
    return k;
} 

int doChange(int k, int l, int r, int x, int dx) {
    int now = ++nowpos;
    copy(now, k);
    if (l == r) {
        sum[now] = dx;
        return now;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) ls[now] = doChange(ls[now], l, mid, x, dx);
    else rs[now] = doChange(rs[now], mid+1, r, x, dx);
    sum[now] = sum[ls[now]] + sum[rs[now]];
    return now;
}

int doQuery(int k, int l, int r, int x, int y) {
    if (r < x || y < l) return 0;
    if (x <= l && r <= y) return sum[k];
    int mid = (l + r) >> 1;
    return doQuery(ls[k], l, mid, x, y) + doQuery(rs[k], mid+1, r, x, y);
}

int query(int a, int b, int x, int y) {
    return doQuery(ver[b], 1, n, x, y)-doQuery(ver[a-1], 1, n, x, y);
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> Q;
    for (int i = 1;i<= n;i++) {
        cin >> a[i];
    }

    for (int i = 1;i<= n;i++) {
        b[i] = {a[i], i};
    }
    sort(b+1, b+n+1, cmp);

    for (int i = 1;i<= n;i++) {
        p[b[i].id] = i;
    }

    pre[0] = 0;
    for (int i = 1;i<= n;i++) {
        pre[i] = max(pre[i-1], p[i]);
    }
    suf[n+1] = inf;
    for (int i = n;i>= 1;i--) {
        suf[i] = min(suf[i+1], p[i]);
    }

    for (int i = 1;i<= n;i++) {
        if (a[i-1] <= a[i]) f[i] = f[i-1];
        else f[i] = i;
    }

    ver[0] = doBuild(1, 1, n);
    for (int i = 1;i<= n;i++) {
        ver[i] = doChange(ver[i-1], 1, n, p[i], 1);
    }

    int a, b, l, r;
    while (Q--) {
        cin >> l >> r;
        if (l < n - r + 1) {
            a = l, b = n - r + 1;
            if (!(pre[a] <= a && suf[b] >= b && f[b-1] <= a)) cout << -1 << '\n';
            else {
                int res = 0;
                if (f[a] > 1) res++;
                if (f[n] > b) res++;
                cout << res << '\n';
            } 
        } else {
            a = n - r + 1, b = l;

            if (f[n] <= 1) { cout << 0 << '\n'; continue; }
            if ((f[n] <= b+1 && suf[b+1] >= b+1) || (f[a-1] <= 1 && pre[a-1] <= a-1)) { cout << 1 << '\n'; continue; }

            int len = b - a + 1;

            int ltr = query(1, b, b+1, n);
            int mtf = query(a, b, b+1, n);

            int rtl = query(a, n, 1, a-1);
            int ftm = query(a, b, 1, a-1);

            cout << max(2, min(max(1 + Ceil(ltr-mtf, len) * 2, Ceil(rtl, len) * 2), max(1 + Ceil(rtl - ftm, len) * 2, Ceil(ltr, len) * 2))) << '\n';
        }
    }
    return 0;
}