【题解】

　　一眼可以想到一个类似二叉树后序遍历的贪心做法，然而这个做法在有相同数字的情况下是错误的。最简单的反例就是n=4,d={1,1,1,2}，正解是1,1,2,1，而贪心是1,1,1,2. 所以这个贪心被叉掉了。

　　我们先把d从大到小排序，然后我们用f[i]表示第i个位置之前（包括i位置）还能取的数的个数。第一个节点显然去第size[1]大的数字就好，如果有多个相等的，那么就取最右边的，因为这可以为后面的节点预留更大的数。当取好一个点的值之后，需要给它的子树预留数字；我们并不能确定子树中的每个节点分别取什么值，但是我们知道子树取的数字一定大于当前节点的数值，所以子树取的值一定在当前节点的数字前面。我们只需要把当前位置及其右边的f[i]减去size即可。每次需要确定一个节点i的取值时，我们只需要找到最大的数值val满足val所在位置右边的c[j]都大于size[i]，如果有多个相等的val，我们还是取最右边的那个。要找到这样的val，我们在线段树上二分就可以了。

　　需要注意的是，在计算到某个父亲的第一个孩子时，我们需要把父亲预留的位置加回来。

　　

1 #include
      
        2 #include
       
         3 #define N 500010 4 #define rg register 5 #define ls (u<<1) 6 #define rs (u<<1|1) 7 using namespace std; 8 int n,m,d[N],siz[N],pos[N],cnt[N]; 9 double k;10 struct tree{11     int l,r,del,mn;12 }a[N<<3];13 inline int read(){14     int k=0,f=1; char c=getchar();15     while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();16     while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar();17     return k*f;18 }19 inline int min(int x,int y){
    return x
        
         y;}21 void build(int u,int l,int r){22     a[u].l=l; a[u].r=r; int mid=(l+r)>>1;23     if(l
         
          >1)) update(ls,l,d);38     a[u].mn=min(a[ls].mn,a[rs].mn);39 }40 int find(int u,int l,int r,int v) {41     if (l==r) {42         if (a[u].mn>=v) return l; return l+1;43     }44     if (a[u].del) pushdown(u);45     int mid=(l+r)>>1;46     if (a[rs].mn>=v) return find(ls,l,mid,v);47     return find(rs,mid+1,r,v);48 }49 int fa(int x) {
    return x/k;}50 int main(){51     n=read(); scanf("%lf",&k); build(1,1,n);52     for(rg int i=1;i<=n;i++) d[i]=read();53     sort(d+1,d+1+n,cmp);54     for(rg int i=n-1;i;i--) if(d[i]==d[i+1]) cnt[i]=cnt[i+1]+1;55     for(rg int i=n;i;i--) siz[fa(i)]+=++siz[i];56     for(rg int i=1;i<=n;i++){57         if(fa(i)&&fa(i)!=fa(i-1)) update(1,pos[fa(i)],siz[fa(i)]-1);58         pos[i]=find(1,1,n,siz[i]); pos[i]+=cnt[pos[i]]; pos[i]-=cnt[pos[i]]++;59         update(1,pos[i],-siz[i]);60     }61     for(rg int i=1;i<=n;i++) printf("%d ",d[pos[i]]);62     return 0;63 }