Luogu

LOJ

分析

先考虑一个贪心。我们把 $d_i$ 从大到小排序，那么每个子树都对应一段区间，我们把儿子按照编号排序，然后把区间依次划分下去即可。

这样子只能通过所有 $d_i$ 互不相同的点，原因是在 $d_i$ 相同时可以通过一些交换使得编号小的点的 $d_i$ 变大。

考虑修正这个贪心。我们维护 $c_i$ 表示 $\leq d_i$ 的可用的难度的个数，那么节点 $u$ 只能选择 $c_i\geq sz_u$ 的 $d_i$，而 $c_i$ 是不降的，所以一定会选最大的那个。

我们按照 BFS 序枚举所有点。假设 $u$ 已经选好了难度，那么其子树中的难度值就只能 $\geq d_i$ 了，又因为我们不知道子树会选择哪些，所以把 $c_{i..n}$ 都减去 $sz_i$，相当于为子树预留位置。在第一次进入某一棵子树时，我们需要把它父亲预留的位置给加回去。

以上操作可以通过线段树实现，找位置可以在线段树上二分。需要注意的是找到的难度可能不是相同的中最靠右的，我们要强制选择最靠右的位置。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;

int n,d[N]; double k;
int fa[N],sz[N],R[N],ans[N];

#define ls (o<<1)
#define rs (o<<1|1)
int minv[N<<2],addv[N<<2];
void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
void pushdown(int o) {
    if (addv[o]) {
        minv[ls]+=addv[o],addv[ls]+=addv[o];
        minv[rs]+=addv[o],addv[rs]+=addv[o];
        addv[o]=0;
    }
}
void build(int o,int l,int r) {
    if (l==r) { minv[o]=l; return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { minv[o]+=w,addv[o]+=w; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
int query(int o,int l,int r,int w) {
    if (l==r) return minv[o]>=w?l:l+1;
    int mid=(l+r)>>1; pushdown(o);
    if (w<=minv[rs]) return query(ls,l,mid,w);
    else return query(rs,mid+1,r,w);
}
#undef ls
#undef rs

int main() {
    n=read(); scanf("%lf",&k);
    for (int i=1;i<=n;++i) d[i]=read();
    sort(d+1,d+n+1,greater<int>()); build(1,1,n);
    for (int i=n;i;--i) R[i]=(d[i]==d[i+1]?R[i+1]:i);
    for (int i=1;i<=n;++i) fa[i]=i/k,sz[i]=1;
    for (int i=n;i;--i) sz[fa[i]]+=sz[i];
    for (int i=1;i<=n;++i) {
        if (fa[i]&&fa[i]!=fa[i-1]) modify(1,1,n,ans[fa[i]],n,sz[fa[i]]-1);
        ans[i]=R[query(1,1,n,sz[i])],modify(1,1,n,ans[i],n,-sz[i]);
    }
    for (int i=1;i<=n;++i) printf("%d%c",d[ans[i]]," \n"[i==n]);
    return 0;
}