2021 插入排序 · 方案二增量维护有序表

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1959 字

改一个元素只挪它自己，询问 O(1)

2021
排序

正文

// CSP-J 2021 复赛 T2 · 插入排序（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2021B
//
// 方案二 · 维护一张有序表，改一个元素只动 O(n)
// 排序结果只取决于 (值, 原下标) 的相对顺序。改一个元素时，
// 整张表的其它部分一点没变，只有被改的那个元素需要挪位置。
// 于是维护数组 ord（按 (值, 原下标) 排好的编号）和 pos[id]（id 在 ord 里的下标）：
//   修改 x：先在 ord 里把 x 摘掉（后面的往前挪一格），改值，
//           再从后往前找到它该待的位置，整体往后挪一格塞进去；
//   询问 x：直接输出 pos[x] + 1，O(1)。
// 一次修改 O(n)，题目保证修改最多 5000 次，5000 * 8000 = 4e7，稳过。
//
// 小提醒：stable_sort 也能得到同样的结果，但每次修改都重排是 O(n log n)，
// 5000 次下来大约是 5e8 次比较，容易被卡常 —— 增量维护更稳。

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

const int MAXN = 8005;
int a[MAXN];
int ord[MAXN];    // 有序表：按 (值, 原下标) 排好的元素编号
int pos[MAXN];    // pos[id] = id 在 ord 中的下标
int len;

// u 是否应该排在 v 前面：先比值，值一样就比原下标（保证稳定）
bool before(int u, int v) {
    if (a[u] != a[v]) return a[u] < a[v];
    return u < v;
}

int main() {
    freopen("sort.in", "r", stdin);
    freopen("sort.out", "w", stdout);

    int n, Q;
    cin >> n >> Q;
    vector<int> ids(n);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ids[i - 1] = i;
    }
    sort(ids.begin(), ids.end(), before);
    len = n;
    for (int i = 0; i < n; i++) {
        ord[i] = ids[i];
        pos[ids[i]] = i;
    }

    while (Q--) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, v;
            cin >> x >> v;
            int p = pos[x];
            for (int i = p; i + 1 < len; i++) {   // 摘掉 x，后面的往前挪
                ord[i] = ord[i + 1];
                pos[ord[i]] = i;
            }
            len--;
            a[x] = v;
            int q = len;
            while (q > 0 && before(x, ord[q - 1])) q--;   // 找新位置
            for (int i = len; i > q; i--) {               // 整体后挪一格
                ord[i] = ord[i - 1];
                pos[ord[i]] = i;
            }
            ord[q] = x;
            pos[x] = q;
            len++;
        } else {
            int x;
            cin >> x;
            cout << pos[x] + 1 << "\n";
        }
    }
    return 0;
}

2021 插入排序 · 方案二 增量维护有序表

正文

CSP-J 标程 · 复赛真题的其它内容

2021 插入排序 · 方案二增量维护有序表