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

__FL__ · 2025-10-10 18:08:46 · 题解

Solution

什么是冒泡排序？

众所周知，在每一次遍历中，我们比较相邻的两个元素，并把更大的放到后面，这样可以保证每一次都将剩下元素中最大的一个扔到最后，所以保证了时间复杂度是 O(n^2)。

这意味着，如果对于一个已经进行了 i 轮冒泡排序的序列来说，它的前 i 大元素会在最后，剩下的则在前面。

因此我们能够得到一个关键结论：对于一个已经进行了 i 轮冒泡排序的序列，它的前 j 个元素恰好是原序列中前 i+j 个元素中的前 j 小。

然后做完了。

每一次询问二，我们用当前序列的前 R 个减去前 (L-1) 个，这时就用到了上述的结论。这是主席树经典用法，类似树上二分，在静态区间第 k 小的基础上加上区间和即可。具体实现可见代码。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500005,M = 1000000000;
int n,a[N],q,cnt,root[N],tot;
struct node
{
    int w,ls,rs,sz;
}f[N<<5];
int update(int root,int l,int r,int x)
{
    f[cnt+1] = f[root];
    root = ++cnt;
    if (l >= r)
    {
        f[root].w += x;
        f[root].sz++;
        return root;
    }
    int mid = (l+r)/2;
    if (x <= mid) f[root].ls = update(f[root].ls,l,mid,x);
    else f[root].rs = update(f[root].rs,mid+1,r,x);
    f[root].w = f[f[root].ls].w+f[f[root].rs].w;
    f[root].sz = f[f[root].ls].sz+f[f[root].rs].sz;
    return root;
}
int query(int root,int l,int r,int k)
{
    if (!k) return 0;
    if (l >= r) return f[root].w/f[root].sz*k;
    int mid = (l+r)/2;
    if (f[f[root].ls].sz >= k) return query(f[root].ls,l,mid,k);
    return f[f[root].ls].w+query(f[root].rs,mid+1,r,k-f[f[root].ls].sz);
}
signed main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        root[i] = root[i-1];
        root[i] = update(root[i],1,M,a[i]);
    }
    cin >> q;
    while (q--)
    {
        int op,l,r;
        cin >> op;
        if (op == 1) tot++;
        else
        {
            cin >> l >> r;
            cout << query(root[min(n,r+tot)],1,M,r)-query(root[min(n,l+tot-1)],1,M,l-1)<< '\n';
        }
    }
    return 0;
}