题目描述
这一天，Konano接到了一个任务，他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n首曲目
，每首曲目都会有一个难度d，游戏内第i首曲目会在玩家Pass第trunc(i/k)首曲目后解锁（x为下取整符号）若tru
nc(i/k)=0，则说明这首曲目无需解锁。举个例子：当k=2时，第1首曲目是无需解锁的（trunc(1/2)=0），第7首曲
目需要玩家Pass第trunc(7/2)=3首曲目才会被解锁。Konano的工作，便是安排这些曲目的顺序，使得每次解锁出的
曲子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个i满足Di≥Dtrun
c(i/k)。当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你，你会怎么解决这份任务呢？
题解
如果这n个数互不相同，那么直接自底向上依次选就好了。
但是如果其中有相同的数，那么直接贪心不能保证字典序最大。
所以还是要从前往后一次考虑。
正解还是比较神仙的。
对于一个位置，要从可选集合中找出最大的x个元素作为这个元素的子树，然后把这x个位置占用一下，到访问到第一个儿子的时候把那x-1个位置再拿出来。
看起来挺简单的，写起来是越写越懵逼。
我们可以把权值从大到小排序，维护一颗线段树，每个节点维护当前位置的左边可选元素个数。
如果那个位置有重复元素，默认选最右边的。
这样可以保证当前选择方案能够最大化兄弟节点的权值。
具体按照代码理解吧。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#define N 500002
using namespace std;
int tr[N<<],la[N<<],num[N],n,size[N],ans[N],a[N];
double k;
bool tag[N];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
inline bool cmp(int a,int b){return a>b;}
inline void pushdown(int cnt){
tr[cnt<<]+=la[cnt];tr[cnt<<|]+=la[cnt];
la[cnt<<]+=la[cnt];la[cnt<<|]+=la[cnt];
la[cnt]=;
}
void build(int cnt,int l,int r){
if(l==r){tr[cnt]=l;return;}
int mid=(l+r)>>;
build(cnt<<,l,mid);build(cnt<<|,mid+,r);
tr[cnt]=min(tr[cnt<<],tr[cnt<<|]);
}
void upd(int cnt,int l,int r,int L,int R,int x){
if(l>=L&&r<=R){
tr[cnt]+=x;la[cnt]+=x;return;
}
int mid=(l+r)>>;
if(la[cnt])pushdown(cnt);
if(mid>=L)upd(cnt<<,l,mid,L,R,x);
if(mid<R)upd(cnt<<|,mid+,r,L,R,x);
tr[cnt]=min(tr[cnt<<],tr[cnt<<|]);
}
int _searsh(int cnt,int l,int r,int x){
if(l==r)return tr[cnt]>=x?l:l+;
int mid=(l+r)>>;
if(la[cnt])pushdown(cnt);
if(tr[cnt<<|]>=x)return _searsh(cnt<<,l,mid,x);
else return _searsh(cnt<<|,mid+,r,x);
}
int main(){
n=rd();scanf("%lf",&k);
for(int i=;i<=n;++i)a[i]=rd();
sort(a+,a+n+,cmp);
for(int i=n;i>=;--i)num[i]=a[i]==a[i+]?num[i+]+:;
build(,,n);
for(int i=n;i>=;--i){
size[i]++;
size[(int)(i/k)]+=size[i];
}
for(int i=;i<=n;++i){
int fa=int((double)i/k);
if(fa&&!tag[fa])upd(,,n,ans[fa],n,size[fa]-),tag[fa]=;
int x=_searsh(,,n,size[i]);
x+=num[x];num[x]++;x-=(num[x]-);
ans[i]=x;
upd(,,n,ans[i],n,-size[i]);
}
for(int i=;i<=n;++i)printf("%d ",a[ans[i]]);
return ;
}