题目

爆炸\(OJ\)机子太慢了吧实在不想打平衡树了

做法

烂大街的一个概念：求中位数

然后求前缀差和后缀差，主席树模板题

注意\(int\)和\(long long\)

My complete code

#include
    
     #pragma GCC optimize (2)#pragma G++ optimize (2)using namespace std;typedef long long LL;inline LL Read(){    LL x(0),f(1); char c=getchar();    while(c<'0' || c>'9'){ if(c=='-')f=-1; c=getchar(); }    while(c>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();    return x*f;}const int inf=0x3f3f3f3f,maxn=1e7+9;int n,k,nod;int size[maxn],son[maxn][2],a[maxn],root[maxn],b[maxn],id[maxn];LL sum[maxn];void Update(int &now,int pre,int l,int r,int x,int val){    now=++nod;    size[now]=size[pre]+1;    sum[now]=sum[pre]+(LL)val;    if(l==r) return;    int mid(l+r>>1);    if(x<=mid){        Update(son[now][0],son[pre][0],l,mid,x,val);        son[now][1]=son[pre][1];    }else{        Update(son[now][1],son[pre][1],mid+1,r,x,val);        son[now][0]=son[pre][0];    }}int Qkth(int now,int pre,int l,int r,int k){    if(l==r) return b[l];    int ret(size[son[now][0]]-size[son[pre][0]]);    int mid(l+r>>1);    if(k>ret) return Qkth(son[now][1],son[pre][1],mid+1,r,k-ret);    else return Qkth(son[now][0],son[pre][0],l,mid,k);}LL Qll(int now,int pre,int l,int r,int x,int val){    if(l==r) return (LL)val-b[l];    int mid(l+r>>1);    if(x<=mid) return Qll(son[now][0],son[pre][0],l,mid,x,val);    else return (LL)(size[son[now][0]]-size[son[pre][0]])*val-(sum[son[now][0]]-sum[son[pre][0]])+Qll(son[now][1],son[pre][1],mid+1,r,x,val);}LL Qbg(int now,int pre,int l,int r,int x,int val){    if(l==r) return b[l]-val;    int mid(l+r>>1);    if(x<=mid) return Qbg(son[now][0],son[pre][0],l,mid,x,val)+(sum[son[now][1]]-sum[son[pre][1]])-(LL)(size[son[now][1]]-size[son[pre][1]])*val;    else return Qbg(son[now][1],son[pre][1],mid+1,r,x,val);}int main(){    n=Read(); k=Read();    for(int i=1;i<=n;++i)        a[i]=b[i]=Read();    sort(b+1,b+1+n);    int cnt=unique(b+1,b+1+n)-b-1;    for(int i=1;i<=n;++i){        id[i]=lower_bound(b+1,b+1+cnt,a[i])-b;        Update(root[i],root[i-1],1,cnt,id[i],a[i]);    }    int mid(k+1>>1),fir,mi;    LL ans(1e18);    for(int l=1;l+k-1<=n;++l){        int r(l+k-1);        LL ret(0);        int zw=Qkth(root[r],root[l-1],1,cnt,mid);        int x=lower_bound(b+1,b+1+cnt,zw)-b;        ret+=Qll(root[r],root[l-1],1,cnt,x,zw);        ret+=Qbg(root[r],root[l-1],1,cnt,x,zw);        if(ret