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

masterhuang · 2025-06-18 11:27:07 · 题解

事实上，这题很简单。发现这个事实，你就会做了。

• 考虑区间求和是与前缀和等价的，于是我们做前缀和。

• 同时考虑对于一个询问，我们只关心之前按了多少次冒泡按钮。

• 我们有如下结论：按冒泡按钮 k 次后，[1,r] 这个前缀和的结果为 [1,\min(r+k,n)] 中前 r 小的和。

这是因为按 k 次时，只有 [1,\min(r+k,n)] 这些位置会对前 r 个数影响。

于是我们在 \min(r+k,n) 这个位置截断数组，只关心前面这些位置。

然后由于冒泡一次会让最大值到最后，两次会让次大值到倒二，以此类推，于是就证明了我们的结论。

对询问离线下来，线段树上二分维护前 k 小的数的和即可。

复杂度 O(n\log n)。

#include<bits/stdc++.h>
#define LL long long
#define ls w<<1
#define rs w<<1|1
#define lw l,m,ls
#define rw m+1,r,rs
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
namespace IO
{
    const int _Pu=2e7+5,_d=32;
    char buf[_Pu],obuf[_Pu],*p1=buf+_Pu,*p2=buf+_Pu,*p3=obuf,*p4=obuf+_Pu-_d;
    inline void fin()
    {
        memmove(buf,p1,p2-p1);
        int rlen=fread(buf+(p2-p1),1,p1-buf,stdin);
        if(p1-rlen>buf) buf[p2-p1+rlen]=EOF;p1=buf;
    }
    inline void fout(){fwrite(obuf,p3-obuf,1,stdout),p3=obuf;}
    inline int rd()
    {
        if(p1+_d>p2) fin();int isne=0,x=0;
        for(;!isdigit(*p1);++p1) isne=(*p1=='-');x=(*p1++-'0');
        for(;isdigit(*p1);++p1) x=x*10+(*p1-'0');
        if(isne) x=-x;return x;
    }
    inline void wr(LL x,char end='\n')
    {
        if(!x) return *p3++='0',*p3++=end,void();
        if(x<0) *p3++='-',x=-x;
        char sta[20],*top=sta;
        do{*top++=(x%10)+'0';x/=10;}while(x);
        do{*p3++=*--top;}while(top!=sta);(*p3++)=end;
    }
}using IO::rd;using IO::wr;
const int N=5e5+5;
int n,m,L,a[N],C,b[N<<2],d[N];LL ans[N],s[N<<2];
struct Q{int k,o,id;};vector<Q>q[N];
inline void add(int r,int c,int o,int id){q[min(r+c,n)].push_back({r,o,id});}
void upd(int p,int l=1,int r=L,int w=1)
{
    if(l==r) return b[w]++,s[w]+=d[p],void();
    int m=(l+r)>>1;p<=m?upd(p,lw):upd(p,rw);
    b[w]=b[ls]+b[rs],s[w]=s[ls]+s[rs];
}
LL qry(int k,int l=1,int r=L,int w=1)
{
    if(l==r) return (LL)k*d[l];int m=(l+r)>>1;
    return (k>b[ls])?qry(k-b[ls],rw)+s[ls]:qry(k,lw);
}
int main()
{
    n=rd();
    for(int i=1;i<=n;i++) a[i]=d[i]=rd();m=rd();
    sort(d+1,d+1+n);L=unique(d+1,d+1+n)-d-1;
    for(int o,l,r,c=0;m--;)
    {
        o=rd();
        if(o==1) c++;
        else
        {
            l=rd(),r=rd();add(r,c,1,++C);
            if(l>1) add(l-1,c,-1,C);
        }
    }
    for(int i=1;i<=n;i++)
    {
        upd(lower_bound(d+1,d+1+L,a[i])-d);
        for(auto [k,o,id]:q[i]) ans[id]+=o*qry(k);
    }
    for(int i=1;i<=C;i++) wr(ans[i]);
    return IO::fout(),0;
}