题目描述
这一天，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<<2],la[N<<2],num[N],n,size[N],ans[N],a[N]; double k; bool tag[N]; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } inline bool cmp(int a,int b){return a>b;} inline void pushdown(int cnt){ tr[cnt<<1]+=la[cnt];tr[cnt<<1|1]+=la[cnt]; la[cnt<<1]+=la[cnt];la[cnt<<1|1]+=la[cnt]; la[cnt]=0; } void build(int cnt,int l,int r){ if(l==r){tr[cnt]=l;return;} int mid=(l+r)>>1; build(cnt<<1,l,mid);build(cnt<<1|1,mid+1,r); tr[cnt]=min(tr[cnt<<1],tr[cnt<<1|1]); } 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)>>1; if(la[cnt])pushdown(cnt); if(mid>=L)upd(cnt<<1,l,mid,L,R,x); if(mid<R)upd(cnt<<1|1,mid+1,r,L,R,x); tr[cnt]=min(tr[cnt<<1],tr[cnt<<1|1]); } int _searsh(int cnt,int l,int r,int x){ if(l==r)return tr[cnt]>=x?l:l+1; int mid=(l+r)>>1; if(la[cnt])pushdown(cnt); if(tr[cnt<<1|1]>=x)return _searsh(cnt<<1,l,mid,x); else return _searsh(cnt<<1|1,mid+1,r,x); } int main(){ n=rd();scanf("%lf",&k); for(int i=1;i<=n;++i)a[i]=rd(); sort(a+1,a+n+1,cmp); for(int i=n;i>=1;--i)num[i]=a[i]==a[i+1]?num[i+1]+1:0; build(1,1,n); for(int i=n;i>=1;--i){ size[i]++; size[(int)(i/k)]+=size[i]; } for(int i=1;i<=n;++i){ int fa=int((double)i/k); if(fa&&!tag[fa])upd(1,1,n,ans[fa],n,size[fa]-1),tag[fa]=1; int x=_searsh(1,1,n,size[i]); x+=num[x];num[x]++;x-=(num[x]-1); ans[i]=x; upd(1,1,n,ans[i],n,-size[i]); } for(int i=1;i<=n;++i)printf("%d ",a[ans[i]]); return 0; }