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

· · 题解

本题

伟大的 carotrl 在 AH 省集中提出冒泡排序若干轮之后的结果是可以直接刻画的。

具体来说说前缀 [1,l] 在经过 c 轮冒泡排序之后的数字构成是原先区间 [1,l+c] 中的前 l 小的数，这个很好理解，经过 c 轮冒泡排序之后，某个数最多往前平移的位置数就是 c，所以范围是 [1,l+c]，而小的数会往前走，所以就是前 l 小。

这样子就可以完成本题了，我们直接拿 [1,r] 经过 c 轮冒泡排序之后的数字组成减去 [1,l-1] 的即可。区间 kth 信息可以直接拿主席树在线维护。时间复杂度 O(n\log n)。

扩展版-区间前 k 小之和

改为若干次操作之后区间 [l,r] 的前 k 小值，如何做？

将上述定理扩展一些，前缀 [1,l] 经过冒泡排序 c 轮之后的前 k 小值为原序列中区间 [1,l+c] 的前 k 小值。

区间 [l,r] 经过 c 轮冒泡排序之后的前 k 小值就是前缀 [1,r+c-1] 中去除前缀 [1,l+c-1] 中的前 l-1 小值之后的前 k 小值，注意这里不能单纯拿两个作差，需要巧妙实现。

还是可以通过主席树在线维护的。本质还是对于两个前缀进行差分，需要设置一个阈值，意思是 [1,l+c-1] 这个区间最多贡献 l-1。具体可以看看代码。

调用 solve(rt[min(l+c-1,n)],rt[min(r+c,n)],1,n,l-1,k) 即可，其中 \rm query 函数就是对于某个版本的主席树区间求和。


    ll solve(int p,int q,int l,int r,int up,int cnt){
        if(l==r) return 1ll*cnt*l;
        int z=val[ls[q]]-min(val[ls[p]],up);
        if(z>=cnt) return solve(ls[p],ls[q],l,mid,up,cnt);
        int del=min(up,val[ls[p]]);
        return sum[ls[q]]-query(0,ls[p],l,mid,del)+solve(rs[p],rs[q],mid+1,r,up-del,cnt-z);
    }

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
int a[maxn],b[maxn],rt[maxn],n,m,q;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct SegmentTree{
    #define mid ((l+r)>>1)
    int val[maxn<<6],ls[maxn<<6],rs[maxn<<6],tot; ll sum[maxn<<6];
    void pushup(int p){ val[p]=val[ls[p]]+val[rs[p]]; sum[p]=sum[ls[p]]+sum[rs[p]]; }
    void build(int &p,int q,int l,int r,int x){
        p=++tot; ls[p]=ls[q]; rs[p]=rs[q];
        val[p]=val[q]; sum[p]=sum[q]; 
        if(l==r){ val[p]++; sum[p]+=b[x]; return ; }
        if(x<=mid) build(ls[p],ls[q],l,mid,x);
        else build(rs[p],rs[q],mid+1,r,x);
        pushup(p);
    }
    ll query(int p,int q,int l,int r,int k){
        if(l==r) return 1ll*k*b[l]; 
        int z=val[ls[q]]-val[ls[p]];
        if(z>=k) return query(ls[p],ls[q],l,mid,k);
        else return sum[ls[q]]-sum[ls[p]]+query(rs[p],rs[q],mid+1,r,k-z);
    }
}seg;
int main(){
    cin>>n; int c=0;
    for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
    sort(b+1,b+1+n); m=unique(b+1,b+1+n)-(b+1); cin>>q;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
    for(int i=1;i<=n;i++) seg.build(rt[i],rt[i-1],1,m,a[i]);
    for(int i=1;i<=q;i++){
        int t,l,r; t=read();
        if(t==1) c++;
        else{
            l=read(); r=read();
            printf("%lld\n",seg.query(rt[0],rt[min(r+c,n)],1,m,r)-seg.query(rt[0],rt[min(l+c-1,n)],1,m,l-1));
        }
    }
    return 0;
}