「九省联考」IIIDX

显然贪心，给每个点填上它能取得的最大点。
对 \(a\) 从小到大排序，维护每个位置对应后缀可用值的个数 \(f\)。
给 \(x\) 填数相当于它右侧减少 \(siz_x\) 个可用值。
查询最大可用值相当于求一段前缀的 \(f\) 都 \(> siz_x\) ，线段树上二分即可。
需要将父亲填充的数去掉。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=5e5+10;
double k;
int n,m,siz[N],fa[N],a[N],v[N],v1[N],cnt,tr[N<<2],tag[N<<2];
int ans[N];
#define ls (t<<1)
#define rs (t<<1|1)
void build(int t,int l,int r){
	if(l==r){
		tr[t]=v1[l];
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);build(rs,mid+1,r);
	tr[t]=min(tr[ls],tr[rs]);
}
void push(int t){
	tr[ls]+=tag[t];tr[rs]+=tag[t];
	tag[ls]+=tag[t];tag[rs]+=tag[t];
	tag[t]=0;
}
void modify(int t,int l,int r,int L,int R,int v){
	if(L<=l && r<=R){
		tr[t]+=v;
		tag[t]+=v;
		return;
	}
	if(tag[t])push(t);
	int mid=l+r>>1;
	if(L<=mid)modify(ls,l,mid,L,R,v);
	if(R>mid)modify(rs,mid+1,r,L,R,v);
	tr[t]=min(tr[ls],tr[rs]);
}
int query(int t,int l,int r,int v){
	if(l==r){
		return tr[t]>=v?l:l-1;
	}
	if(tag[t])push(t);
	int mid=l+r>>1;
	if(tr[ls]>=v)return query(rs,mid+1,r,v);
	return query(ls,l,mid,v);
}
#undef ls
#undef rs
pair<int,int> q[N];
void init(){
	fo(i,1,n)q[i]=make_pair(a[i],i);
	sort(q+1,q+n+1);
	fo(i,1,n){
		if(q[i].first!=q[i-1].first)v[++m]=q[i].first,v1[m]=n-i+1;
		a[q[i].second]=m;
	}
	build(1,1,m);
}
int main(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	scanf("%d%lf",&n,&k);
	fo(i,1,n)scanf("%d",&a[i]);
	init();
	fd(i,n,1){
		++siz[i];
		int x=(int)(1.0*i/k);
		fa[i]=x;
		siz[x]+=siz[i];
	}
	fo(i,1,n){
		if(fa[i]!=fa[i-1]){
			modify(1,1,m,1,ans[fa[i]],siz[fa[i]]-1);
		}
		ans[i]=query(1,1,m,siz[i]);
		modify(1,1,m,1,ans[i],-siz[i]);
	}
	fo(i,1,n)printf("%d ",v[ans[i]]);
	printf("\n");

	return 0;
}