Link.
Description.
给定一棵树，第 \(i\) 个点的父亲是 \(\lfloor\frac ik\rfloor\)。
有一些权值，你需要对每个节点附上一个权值，满足每个点都比他所有后代小，使得权值构成的序列字典序最大。
Solution.
逐位确定。
第 \(i\) 位填完后，相当于多了一个限制，就是至少有 \(sz_i-1\) 个数 \(\ge b_i\)。
注意这个限制在一个节点所有孩子被确定后会消失，因为都变成了孩子自己的限制了。
考虑维护这件事情：
- 插入一个形如要至少有 \(k\) 个数 \(\ge b\) 的限制
- 删除一个限制
- 找到一个最大的可以被取的数
- 删掉一个数
考虑 \(f_i\) 表示只考虑 \(b\ge i\) 的限制有多少个可以取。
则初始就是出现个数的后缀和。
我们每次要找到一个最后面的满足 \(f_i\ge sz\)，这个可以线段树二分，维护前缀 \(\min\)。
多一个限制相当于前缀减 \(k\)，少一个数相当于前缀减 \(1\)。
然后就做完了。
Coding.
点击查看代码
//是啊……你就是那只鬼了……所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=1;
for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
if(f) x=-x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}//}}}
const int N=500005;double k;
int n,ut,w[N],fa[N],tn[N],rs[N],sz[N],tg[N],cn[N];
namespace segment
{
struct seg{int mn,tg;}T[N<<2];
inline void pushup(int x) {T[x].mn=min(T[x<<1].mn,T[x<<1|1].mn);}
inline void allc(int x,int w) {T[x].mn+=w,T[x].tg+=w;}
inline void pushdw(int x) {if(T[x].tg) allc(x<<1,T[x].tg),allc(x<<1|1,T[x].tg),T[x].tg=0;}
inline void build(int x,int l,int r)
{
if(l==r) return T[x].mn=cn[l],void();
build(x<<1,l,(l+r)>>1),build(x<<1|1,((l+r)>>1)+1,r),pushup(x);
}
inline void modif(int x,int l,int r,int dl,int dr,int dc)
{
if(l>dr||dl>r) return;else if(dl<=l&&r<=dr) return allc(x,dc);else pushdw(x);
modif(x<<1,l,(l+r)>>1,dl,dr,dc),modif(x<<1|1,((l+r)>>1)+1,r,dl,dr,dc),pushup(x);
}
inline int query(int x,int l,int r,int k)
{
if(l==r) return l;else pushdw(x);
if(T[x<<1].mn<k) return query(x<<1,l,(l+r)>>1,k);
else return query(x<<1|1,((l+r)>>1)+1,r,k);
}
inline int qry(int w) {return T[1].mn>=w?ut:query(1,1,ut,w)-1;}
inline void debug(int x,int l,int r)
{
if(l==r) return printf("%d ",T[x].mn),void();else pushdw(x);
debug(x<<1,l,(l+r)>>1),debug(x<<1|1,((l+r)>>1)+1,r);
}
}using namespace segment;
int main()
{
read(n),scanf("%lf",&k);for(int i=1;i<=n;i++) read(w[i]),sz[i]=1;
for(int i=1;i<=n;i++) fa[i]=int(i/k),tn[++ut]=w[i];
sort(tn+1,tn+ut+1),ut=unique(tn+1,tn+ut+1)-tn-1;
for(int i=1;i<=n;i++) ++cn[w[i]=lower_bound(tn+1,tn+ut+1,w[i])-tn];
for(int i=ut;i>=1;i--) cn[i]+=cn[i+1];
sz[0]=1;for(int i=n;i>=1;i--) sz[fa[i]]+=sz[i];
//for(int i=0;i<=n;i++) printf("%d%c",sz[i],i==n?'\n':' ');
tg[0]=1,build(1,1,ut);
for(int i=1,v;i<=n;i++)
{
if(!tg[fa[i]]) modif(1,1,ut,1,rs[fa[i]],sz[fa[i]]-1),tg[fa[i]]=1;
//debug(1,1,ut),putchar('\n');
rs[i]=v=qry(sz[i]),modif(1,1,ut,1,v,-sz[i]);
//printf("! %d ( %d %d\n",v,i,sz[i]);
}
for(int i=1;i<=n;i++) printf("%d%c",tn[rs[i]],i==n?'\n':' ');
return 0;
}