P14085 [ICPC 2023 Seoul R] Apricot Seeds 題解

· · 题解

好牛啊這個。

有這樣一個結論，對於一個前綴 [1,x]，經過 k 輪的冒泡排序，[1,x] 的數字會變成 [1,x+k] 的前 x 小的數字。

::::info[證明]

首先 [x+k+1,n] 的數字肯定不可能出現，因為每個數字每次最多左移一位。

進過 k 輪之後，[1,x+k] 中前 k 大的數字必然已經不在 [1,x] 的位置內，因此 [1,x] 只能是 [1,x+k] 中前 x 小的數字。

::::

這道題目每次操作相當於抽出來一個子區間做操作然後子區間內區間查詢，先轉成前綴和形式然後主席樹實現查詢前 k 小的和即可。

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+5;
int n,m,A[N],Rt[N],TOT;
struct Tree{int L,R,Sz;LL S;}t[N*50];
#define Ls(x) t[x].L
#define Rs(x) t[x].R
#define Mid (L+R>>1)
void Upd(int &u,int L,int R,int x)
{
    t[++TOT]=t[u],u=TOT;
    t[u].Sz++,t[u].S+=x;
    if(L==R)return;
    if(x<=Mid)Upd(Ls(u),L,Mid,x);
    else Upd(Rs(u),Mid+1,R,x);
}
LL Qry(int u,int u2,int L,int R,int x)
{
    if(L==R)return 1ll*x*L;
    if(x<=t[Ls(u)].Sz-t[Ls(u2)].Sz)return Qry(Ls(u),Ls(u2),L,Mid,x);
    return t[Ls(u)].S-t[Ls(u2)].S+Qry(Rs(u),Rs(u2),Mid+1,R,x-(t[Ls(u)].Sz-t[Ls(u2)].Sz));
}
const int Inf=1e9;
inline LL Qry(int L,int R,int x,int v)
{
    if(!v)return 0;
    return Qry(Rt[min(R,L+v+x-1)],Rt[L-1],1,Inf,v);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&A[i]),Rt[i]=Rt[i-1],Upd(Rt[i],1,Inf,A[i]);
    for(int i=1,L,R,t,x,y;i<=m;i++)
    {
        scanf("%d%d%d%d%d",&L,&R,&t,&x,&y);
        printf("%lld\n",Qry(L,R,t,y)-Qry(L,R,t,x-1));
    }
}