这什么鬼题，送的55分要拿稳，实测有60？

考虑把数值从大到小摆好，每个位置\(i\)维护一个\(f_i\)，表示\(i\)左边比它大的（包括自己）还有几个数可以选

这个最开始直接处理好，就是>=数值\(i\)的数字个数

如果我们从小到大安排，发现我们需要给当前数安排一个数值，根据贪心，这个数值要尽可能大，但又要满足一个条件，就是这个数值右边的\(\min \{f_i\}\ge siz_{now}\)

安排完了以后，需要给子树再安排一下，就把右边区间的\(f_i\)做一个区间减

然后注意一个事情，进入子树以后，子树会去安排子树，所以在进子树第一个点后要把父亲的安排撤回。

感性一点理解的说，就是贪心的选一个可以选的最大值，需要保证还有一定数目的更大值可以在后面被选，但是你不知道到底这个后面的最大值怎么被选了，于是先维护好已经被选了一定个数这个信息，后面再去安排它。你现在安排它是为了排在它后面的同层点不去干扰它们

---

Code:

#include 
    
     #include 
     
      using std::min;const int N=5e5+10;const double eps=1e-6;int n,d[N],b[N],par[N],pos[N],yuu[N],siz[N];double k;#define ls id<<1#define rs id<<1|1int mi[N<<2],tag[N<<2];void build(int id,int l,int r){    if(l==r) {mi[id]=yuu[l];return;}    int mid=l+r>>1;    build(ls,l,mid),build(rs,mid+1,r);    mi[id]=min(mi[ls],mi[rs]);}void pushdown(int id){    if(tag[id])    {        mi[ls]+=tag[id];        mi[rs]+=tag[id];        tag[ls]+=tag[id];        tag[rs]+=tag[id];        tag[id]=0;    }}void ins(int id,int L,int R,int l,int r,int d){    if(l==L&&r==R)    {        mi[id]+=d;        tag[id]+=d;        return;    }    pushdown(id);    int Mid=L+R>>1;    if(r<=Mid) ins(ls,L,Mid,l,r,d);    else if(l>Mid) ins(rs,Mid+1,R,l,r,d);    else ins(ls,L,Mid,l,Mid,d),ins(rs,Mid+1,R,Mid+1,r,d);    mi[id]=min(mi[ls],mi[rs]);}int query(int id,int l,int r,int s){    if(l==r) return mi[id]>=s?l:l+1;    pushdown(id);    int mid=l+r>>1;    if(mi[rs]>=s) return query(ls,l,mid,s);    else return query(rs,mid+1,r,s);}int main(){    scanf("%d%lf",&n,&k);    for(int i=1;i<=n;i++) scanf("%d",d+i),par[i]=1.0*i/k+eps;    std::sort(d+1,d+1+n);    int m=0,p=1;b[p]=d[n];    for(int i=1;i<=n;i++) if(d[i]!=d[i-1]) ++m;    for(int i=n-1;~i;i--)        if(d[i]!=d[i+1])        {            yuu[p]=n-i;            b[++p]=d[i];        }    build(1,1,m);    for(int i=n;i;i--) ++siz[i],siz[par[i]]+=siz[i];    for(int i=1;i<=n;i++)    {        if(par[i]&&par[i]!=par[i-1]) ins(1,1,m,pos[par[i]],m,siz[par[i]]-1);        pos[i]=query(1,1,m,siz[i]);        printf("%d ",b[pos[i]]);        ins(1,1,m,pos[i],m,-siz[i]);    }    return 0;}
     
    

---

2019.3.18