分析

放学了先咕了。

代码

#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN=500005;

int n,d[MAXN];
int ecnt,head[MAXN],siz[MAXN],ans[MAXN];
double k;
int sum[MAXN<<2],loc,ql,qr,kk;

struct Edge{
    int to,nxt;
}e[MAXN<<1];

inline void add_edge(int bg,int ed){
    ++ecnt;
    e[ecnt].to=ed;
    e[ecnt].nxt=head[bg];
    head[bg]=ecnt;
}

#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc ((o<<1)|1)

void upd(int o,int l,int r){
    if(l==r){
        sum[o]+=kk;
        return;
    }
    if(loc<=mid) upd(lc,l,mid);
    else upd(rc,mid+1,r);
    sum[o]=sum[lc]+sum[rc];
}

int query(int o,int l,int r){
    if(l==r) return l;
    if(sum[rc]>=kk) return query(rc,mid+1,r);
    else return kk-=sum[rc],query(lc,l,mid);
}

#undef mid
#undef lc
#undef rc

int main(){
    n=read();
    scanf("%lf",&k);
    rin(i,1,n) d[i]=read(),siz[i]=1;
    std::sort(d+1,d+n+1);
    rin(i,1,n) add_edge((int)floor(i/k),i);
    irin(i,n,1) siz[(int)floor(i/k)]+=siz[i];
    trav(i,0){int ver=e[i].to;loc=ver,kk=siz[ver];upd(1,1,n);}
    int cnt=1;
    rin(i,2,n+1){
        if(d[i]==d[i-1]){#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

const int MAXN=500005;

int n,d[MAXN];
int ecnt,head[MAXN],siz[MAXN],ans[MAXN];
double k;
int sum[MAXN<<2],loc,ql,qr,kk;

struct Edge{
    int to,nxt;
}e[MAXN<<1];

inline void add_edge(int bg,int ed){
    ++ecnt;
    e[ecnt].to=ed;
    e[ecnt].nxt=head[bg];
    head[bg]=ecnt;
}

#define mid ((l+r)>>1)
#define lc (o<<1)
#define rc ((o<<1)|1)

void upd(int o,int l,int r){
    if(l==r){
        sum[o]+=kk;
        return;
    }
    if(loc<=mid) upd(lc,l,mid);
    else upd(rc,mid+1,r);
    sum[o]=sum[lc]+sum[rc];
}

int query(int o,int l,int r){
    if(l==r) return l;
    if(sum[rc]>=kk) return query(rc,mid+1,r);
    else return kk-=sum[rc],query(lc,l,mid);
}

#undef mid
#undef lc
#undef rc

int main(){
    n=read();
    scanf("%lf",&k);
    rin(i,1,n) d[i]=read(),siz[i]=1;
    std::sort(d+1,d+n+1);
    rin(i,1,n) add_edge((int)floor(i/k),i);
    irin(i,n,1) siz[(int)floor(i/k)]+=siz[i];
    trav(i,0){int ver=e[i].to;loc=ver,kk=siz[ver];upd(1,1,n);}
    int cnt=1;
    rin(i,2,n+1){
        if(d[i]==d[i-1]){
            ++cnt;
            continue;
        }
        irin(j,cnt,1){
            kk=j;int ret=query(1,1,n);ans[ret]=d[i-1];
            loc=ret,kk=-siz[ret];upd(1,1,n);
            trav(l,ret){
                int ver=e[l].to;
                loc=ver,kk=siz[ver];upd(1,1,n);
            }
        }
        cnt=1;
    }
    rin(i,1,n) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}
            ++cnt;
            continue;
        }
        irin(j,cnt,1){
            kk=j;int ret=query(1,1,n);ans[ret]=d[i-1];
            loc=ret,kk=-siz[ret];upd(1,1,n);
            trav(l,ret){
                int ver=e[l].to;
                loc=ver,kk=siz[ver];upd(1,1,n);
            }
        }
        cnt=1;
    }
    rin(i,1,n) printf("%d ",ans[i]);
    printf("\n");
    return 0;
}