题解：P12865 [JOI Open 2025] 冒泡排序机 / Bubble Sort Machine

Qing_Hyun · 2025-11-10 21:42:08 · 题解

双倍经验：本题强化版（区间冒泡）。

有一个经典结论，对于一个前缀 [1,x]，经过 k 轮的冒泡排序，[1,x] 的数字会变成 [1,x + k] 的前 x 小的数字。

这道题目相当于对一个子区间做 k 次操作子区间，可持久化权值线段树（Persistent Segment Tree）实现查询前 k 小的和即可。

维护前缀和只需要多记一个前缀和数组即可。

:::info[Code]

#include<bits/stdc++.h>
//#define int long long
#define fo(i, a, b) for(int i = a; i <= b; i ++)
#define fd(i, a, b) for(int i = a; i >= b; i --)
#define ll long long

using namespace std;

const int N = 1e6 + 5, INF = 1e9 + 7;

int n, q;
int a[N];

int cnt;

int rt[N], tot;
struct SegT {
    int ls, rs, num;
    ll sum;
} tr[N << 5];

void Insert(int &o, int oth, int l, int r, int v) {
    o = ++ cnt;
    tr[o] = tr[oth];
    tr[o].num ++;
    tr[o].sum += v;
    if(l == r)
        return;
    int mid = l + r >> 1;
    if(v <= mid)
        Insert(tr[o].ls, tr[oth].ls, l, mid, v);
    else
        Insert(tr[o].rs, tr[oth].rs, mid + 1, r, v);
//  cout << tr[o].num << " " << tr[o].sum << "***\n";
}

inline ll Query(int o, int oth, int x, int y, int p) {
    if(x >= y)
        return (ll)p * x;
    int s = tr[tr[o].ls].num - tr[tr[oth].ls].num, mid = x + y >> 1;
    if(s >= p)
        return Query(tr[o].ls, tr[oth].ls, x, mid, p);
    else
        return tr[tr[o].ls].sum - tr[tr[oth].ls].sum + Query(tr[o].rs, tr[oth].rs, mid + 1, y, p - s);
}

ll Check(int l, int r, int k, int p) {
    int x = min(r, l + p + k - 1), y = l - 1;
    return Query(rt[x], rt[y], 1, INF, p);
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;

    fo(i, 1, n)
    cin >> a[i], Insert(rt[i], rt[i - 1], 1, INF, a[i]);
    cin >> q;
    int type, k = 0, l = 1, r = n;
    fo(i, 1, q) {
        int x, y;
        cin >> type;
        if(type == 1) {
            k ++;
            continue;
        }
        cin >> x >> y;
        ll ans = Check(l, r, k, y) - Check(l, r, k, x - 1);
        cout << ans << "\n";
    }
    return 0;
}

:::