题解：P17136 [KOI 2026 #1] 数列排序

wanganze · 2026-07-24 01:37:10 · 题解

题意

一种特殊的排序方式：对于 A 每次指定一个阈值 x，把 \le x 的数字放到新序列 B，否则放到 C，序列 B 和 C 拼接得到新序列。求序列 a 最优情况下的操作次数。

分析

考虑一对逆序对 a_i>a_j\ (i<j) 什么时候会被消除：只有某次操作的 x 满足 a_j\le x <a_i 才会消除逆序对，即 x\in [a_j,a_i - 1]。

那我们就把问题转化为了值域上的区间覆盖问题。

但是逆序对最大可以达到 O(n^2) 对，直接贪心显然不行，但是我们依然可以“按右端点排序”。我们记录 a_i 的第一次和最后一次出现的坐标 fir_{a_i},lst_{a_i}，那么对于 p > q，如果 lst_{q}>fir_{p}，就存在逆序对。

从小到大枚举阈值 x，对于所有未被操作的 q 求 pos=\max lst_{q}。如果 pos>fir_{x+1} 说明构成逆序对我们需要在此处操作，而操作之后当前的所有 q 都已经被移到前面，pos 归零即可。

实现

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int fir[N],lst[N]; 
int main()
{
    int n;
    cin>>n;
    for(int i = 1,x; i <= n; i ++)
    {
        cin>>x;
        if(!fir[x]) fir[x] = i;
        lst[x] = i;
    }
    int res = 0,p = 0;
    for(int i = 1; i < n; i ++)
    {
        p = max(p,lst[i]);
        if(fir[i + 1] && p > fir[i + 1]) res ++,p = 0;
    }
    cout<<res<<'\n';
    return 0;
}