题目：
给出 k 和 n 个数，构造一个序列使得 d[i]>=d[i/k] ，并且字典序最大。
分析：
听说，当年省选的时候，这道题挡住了大批的高手，看上去十分简单，实际上那道弯段时间内是转不过来的。
首先，一个套路是，将这个序列的关系抽象成一棵树，i的父亲是floor(i/k)，我们要要求子树内部的点的权值都比父亲大。
我们观察子任务的特殊限制，di不一样？
我们想，把原序列从大到小排序，在树上dfs给点赋值，在给一个点赋值时，要在序列上预留出siz[这棵子树]的位置，用来给子树内部的点赋值（排序就是为了方便在序列上预留位置）。
但是，如果有重复的元素就办不了了，比如n=4， k=2 序列是1，1，1，2.
排好应该是1 1 2 1，但是我们上面的方法会排成1 1 1 2
为什么呢？
我们从大到小排序，应该得到2 1 1 1.我们递归，首先是树根节点，需要预留4个位置，所以肯定要选最后一个（1），然后递归到第一个子树（序号为2），size为2，需要在这个子树留两个位置，所以我们把第二个1给了序号2这个位置，然后那个2就给了它的儿子（序号4）但是实际上，我们可以给它留一个1，把这个4给位置3.
我这么分析会很乱，但是我们于情于理考虑一下，我们解决完了位置2，若想字典序最大，我们应该先最大化3这个位置。
所以我们应该在给序号2找到最大值之后，应该为他的子树预留一些值，使这些值在合法的基础上尽可能小。
所以我们应该排序后，建立一个序列c，c[i]的值代表排好序的序列上，i及i左边的所有值还剩下多少个可以选的。
（序列c一开始肯定是1,2,3,4,5……）
然后我们每次为一个点赋值，应该找到最靠左的一个位置i，使所有j>=i满足c[j]>=siz[这个点的子树]。
并且选完之后，要找到这个位置往右最右边和他值相等的那个位置（前提是没有被用过的）。
然后，用区间减法计算贡献，之后接着处理这个点的兄弟节点，没有了兄弟节点之后在进入某个点的子节点。
进入一个子节点时，要将之前预留的位置（区间减去的数值）加回来，但是已经分配出去的（父亲的）权值就不要加回来了。
所以是siz-1
代码：
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=,inf=1e9;
struct segtree{
int l,r,ls,rs,mn,lz;
}t[N*];int a[N],b[N],ans[N],m,rt;
db k;int n,siz[N],fa[N],cnt[N],o=;
bool cmp(int u,int v){return u>v;}
void pushup(int cur){
int ls=t[cur].ls,rs=t[cur].rs;
t[cur].l=t[ls].l;t[cur].r=t[rs].r;
t[cur].mn=min(t[ls].mn,t[rs].mn);
} void pushdown(int cur){
int ls=t[cur].ls,rs=t[cur].rs,d=t[cur].lz;
t[ls].mn+=d;t[ls].lz+=d;
t[rs].mn+=d;t[rs].lz+=d;
t[cur].lz=;return ;
} void build(int x,int l,int r){
if(l==r){
t[x].l=t[x].r=l;t[x].ls=t[x].rs=-;
t[x].mn=l;return ;
} int mid=l+r>>;
t[x].ls=o++;t[x].rs=o++;
build(t[x].ls,l,mid);build(t[x].rs,mid+,r);
pushup(x);return ;
} void update(int x,int l,int r,int c){
if(l<=t[x].l&&t[x].r<=r)
{t[x].mn+=c;t[x].lz+=c;return ;}
pushdown(x);int mid=t[x].l+t[x].r>>;
if(l<=mid) update(t[x].ls,l,r,c);
if(mid<r) update(t[x].rs,l,r,c);
pushup(x);return ;
} int query(int x,int p){
if(t[x].l==t[x].r)
return t[x].mn>=p?t[x].l:t[x].l+;
pushdown(x);int mid=t[x].l+t[x].r>>;
if(p<=t[t[x].rs].mn) return query(t[x].ls,p);
else return query(t[x].rs,p);return ;
} int main(){
scanf("%d%lf",&n,&k);rt=o++;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
sort(a+,a++n,cmp);build(rt,,n);
for(int i=n-;i;i--)
if(a[i]==a[i+]) cnt[i]=cnt[i+]+;
else cnt[i]=;
for(int i=;i<=n;i++)
fa[i]=(int)floor(i/k),siz[i]=;
for(int i=n;i;i--) siz[fa[i]]+=siz[i];
for(int i=;i<=n;i++){
if(fa[i]&&fa[i]!=fa[i-])
update(rt,ans[fa[i]],n,siz[fa[i]]-);
int x=query(rt,siz[i]);ans[i]=x;
x+=cnt[x];cnt[x]++;x-=(cnt[x]-);
update(rt,x,n,-siz[i]);
} for(int i=;i<=n;i++)
printf("%d ",a[ans[i]]);
return ;
}
贪心+线段树