Description:

给出 $N$ 个数，求一个字典序最大的序列使得满足所有 $ D_i $ $\ge $ $D_{\lfloor\frac{i}{k}\rfloor} $

$ 1\le N \le 500000 $

Solution:

把限制关系抽象成树，那么一个贪心思路是按树的后序遍历选值，但是这种做法在有多个重复值时会出错，分析一下出错原因会发现是因为当有多个值相同时可以选择相同的值中的最后一个以达到将更多大的数让出来的目的，可以设计出这样一个算法：对于当前正在处理的数 $i $ ，设它的子树大小为 $ siz_i $ ，则选择没有选过的第 $ siz_i $ 个数，如果有多个相同的数，则选择最后一个，且为他的子树预留 $ siz_i-1 $ 个比它大数，用线段树二分 $ + $ 区间加实现选择和预留的过程，线段树里存还有多少个可选的数比这个数大，这个值显然是单调的，可以通过二分查找，预留时应对于比当前答案大的数都减去子树大小，注意每次选择时要先除去他父亲为他预留的标记

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector>

#include<cstring>

using namespace std;

#define MAXN 500010

#define eps 1e-8

double k;

int n,a[MAXN],fa[MAXN],siz[MAXN],res[MAXN];

map<int,vector<int> > p;

void init()

{

	cin >> n >> k;

	for(int i = 1;i <= n;++i){fa[i] = (int)((double)i / k + eps);}

	for(int i = n;i >= 1;--i){siz[i] += 1;siz[fa[i]] += siz[i];}

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	sort(a + 1,a + 1 + n,greater<int>());

	for(int i = 1;i <= n;++i)p[a[i]].push_back(i);

	return;

}

struct node

{

	int lc,rc,tag,minv;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void build(int rt,int l,int r)

{

	if(l == r){t[rt].tag = 0;t[rt].minv = l;return;}

	int mid = ((l + r) >> 1);

	build(t[rt].lc = newnode(),l,mid);

	build(t[rt].rc = newnode(),mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag == 0)return;

	t[t[rt].lc].minv += t[rt].tag;t[t[rt].lc].tag += t[rt].tag;

	t[t[rt].rc].minv += t[rt].tag;t[t[rt].rc].tag += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,int v,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].tag += v;

		t[rt].minv += v;

		return;

	}

	pushdown(rt);

	int mid = ((l + r) >> 1);

	if(L <= mid)add(t[rt].lc,L,R,v,l,mid);

	if(R >= mid + 1)add(t[rt].rc,L,R,v,mid + 1,r);

	t[rt].minv = min(t[t[rt].lc].minv,t[t[rt].rc].minv);

	return;

}

int query(int v)

{

	int cur = root,l = 1,r = n;

	while(l != r)

	{

		pushdown(cur);

		if(t[t[cur].rc].minv >= v){cur = t[cur].lc;r = ((l + r) >> 1);}

		else{cur = t[cur].rc;l = ((l + r) >> 1) + 1;}

	}

	return (t[cur].minv >= v ? l : l + 1);

}

int main()

{

	init();

	build(root = newnode(),1,n);

	for(int i = 1;i <= n;++i)

	{

		if(fa[i])add(root,res[fa[i]],n,siz[i],1,n);

		int k = query(siz[i]);

		res[i] = p[a[k]].back();p[a[k]].pop_back();

		add(root,res[i],n,-siz[i],1,n);

	}

	for(int i = 1;i <= n;++i)printf("%d ",a[res[i]]);

	return 0;

}