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

· · 题解

昨晚想了一个小时没想出来，今天吃早饭的时候突然会了，感觉这个题很牛。

此题貌似是并不需要可持久化线段树的，可能是我太菜了没想到。

首先我们看一下题目给的提示，想一下 1\leq A_i\leq 2 怎么做，我们打表观察一下，发现每按一次一号按钮，每一个 2 都会移动到下一个 2 的前面一个位置。这相当于所有的 2 前移一位，然后第一个 2 移动到序列末尾，证明是容易的。

那么接着考虑把这个规律扩展到一般的情况。我们想一下每次向后移动的到底是什么。如果 a_i 的前面存在一个严格大于 a_i 的数，那么在操作完 1\sim i-2 之后，要么是这个数移动到了 a_{i-1} 的位置，要么是一个比这个数更大的数把它挡住了，然后更大的数继续往后移动。所以只要 a_i 之前存在一个严格大于 a_i 的数，那么 a_i 一定只会往前移动一个位置，否则 a_i 就会开始往后移。所以我们发现每次往后移动的其实就是前缀最大值(不一定严格)，然后其他的位置全部前移一位。

那么我们考虑一下怎么利用这个规律来做这个题。我们考虑把前缀最大值和非前缀最大值分开来维护，最后再加起来就好。

首先我们不难证明，一个数只要在某一次操作之后变成了前缀最大值，就再也不会变回非前缀最大值了，假设我们已经知道了每次操作会有哪些数变成前缀最大值。

非前缀最大值的维护是简单的，只需要支持整体向前平移和删除一些数就行了，树状数组简单维护即可。

前缀最大值需要支持每次将所有数移动到它后一个有数的位置，然后整体前移，再删除队首和添加队尾，以及向中间添加一些数。这个东西如何做呢，我们先维护哪些位置是有前缀最大值的，这个是简单的，每次只需要删除第一个，末尾添加一个，整体平移即可，依旧树状数组维护。然后我们查询的时候就可以知道要查前缀最大值中的第几个到第几个的和了。然后我们又不难发现，前缀最大值在原序列中一定是从小到大出现的。我们在每次相当于查询其中前 k 大的和，理论可以用平衡树维护，但是那样难写且常数大，我们直接开两个树状数组，把每个数存储在他在原数组中的数从小到大排名的位置，一个给每一个位置加一用来查询第 k 大在原数组中排名第几，另外一个用来计算前缀和。

最后还有一步就是求出每一个数到底什么时候开始成为前缀最大值，这个也是简单的，我们只根据前面注意到的性质，每一次操作时，每一个非前缀最大值都会有一个严格大于它的数从它前面移动到后面，也就是说只需要统计这个数前面有几个严格大于它的就行了。

因为 A_i 是 10^9 的，不要忘记离散化。

这样我们开四个树状数组就做完了，总复杂度 O((n+q)\log n)，看似难写但是代码并不长。

#include<bits/stdc++.h>
#define N 500009
#define ll long long
using namespace std;
struct BIT{
    ll c[N<<1],n;
    void init(int n_){
        n=n_;memset(c,0,sizeof(c));
    }
    void add(int x,ll v){
        for(;x<=n;x+=(x&-x))c[x]+=v;
    }
    ll sum(int x){
        ll ret=0;for(;x;x-=(x&-x))ret+=c[x];return ret;
    }
    int get(ll x){
        ll ret=0;
        for(int i=__lg(n);~i;--i){
            if((ret|(1<<i))<=n&&c[ret|(1<<i)]<=x){
                ret|=(1<<i);x-=c[ret];
            }
        }
        return ret;
    }
} f,g,p,pos;
basic_string<int> h[N];
int n,q,tot,a[N],c[N],rk[N];
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;for(int i=1;i<=n;i++) cin>>a[i],c[i]=a[i];
    sort(c+1,c+n+1);tot=unique(c+1,c+n+1)-c-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(c+1,c+tot+1,a[i])-c,rk[a[i]]++;
    for(int i=1;i<=tot;i++) rk[i]+=rk[i-1];
    cin>>q;
    f.init(tot);g.init(n<<1);
    for(int i=1;i<=n;i++){
        h[i-f.sum(a[i])]+=i;
        f.add(a[i],1);
        g.add(i,c[a[i]]);
    }
    f.init(n);p.init((n<<1));pos.init(n);
    for(int i=1,op,l,r,cnt=0;i<=q;i++){
        cin>>op;
        if(op==1){
            if(cnt>=n)continue;
            ++cnt;
            for(int j:h[cnt]){
                g.add(j,-c[a[j]]);
                p.add(j,1);
                f.add(rk[a[j]],c[a[j]]);
                pos.add(rk[a[j]],1);
                --rk[a[j]];
            }
            p.add(cnt,-1);
            p.add(n+cnt,1);
        }
        else{
            cin>>l>>r;
            ll ans=g.sum(cnt+r)-g.sum(cnt+l-1);
            int x=p.sum(cnt+l-1);x=pos.get(x);
            ans-=f.sum(x);
            x=p.sum(cnt+r);x=pos.get(x);
            ans+=f.sum(x);
            cout<<ans<<"\n";
        }
    }
    return 0;
}