2018 省选 D1T2 IIIDX
枫林晚
2018-04-14 10:57:59
### 题目大意：
给出k、n个数选择一种字典序最大的排列，使得对于任意的i，di>=d[i/k](下取整 下同）
### 分析：
很容易想到的是建树，将i的父亲设为[i/k]，之后建有向边。
#### 60分贪心：
将原先的a数组升序排列，直接根据子树大小分配排位。pai[i]=(同层级剩余的)-(子树大小)+1;
然而对于di有相同的情况时，也许可能会使得子树之间值发生交换，仍使得命题成立。
例如：
[1,2,2,3] k=2;
正解：[1,2,3,2]
贪心: [1,2,2,3]
问题在于，因为题目中说了满足单调不降即可，而贪心则极力向后取数，可能会将大的数预留给自己较大编号的后代。如这个例子中，2号取到了3号排位，将4号排位、最大的3留给了4号。而3号就只剩下了2号排位。
我们想最大化较小的编号的值，就让它尽量往后取排位。
但是由于单调不降，可以让2号取2号位，4号取3号位，3号取4号位。使得答案更优。
#### 正解：
线段树。
令原数组a降序排列。
**令f[i]表示i号排位左边还有几个位置上的数是可以取到的。线段树维护这个区间内f的最小值。
**
显然这个f数组单调不降。对于从小到大的第i个编号，我们每次二分一个x，使得找到一个最靠左的位置，使得f[x]>=size[i]，若有多个x，找到最靠右的一个x（这样使得在x取值最优时，尽可能将大的数留给后面的数。）让[x~n]区间上的值都减去size[i]
#### 具体实现：
1.先判断到了i号点时，有没有进入下一个层级，如果有，将**上一个层级预留的值都加回来**（+size[fa]-1），才能二分、利用。
2.二分找到一个p；将p移动到同一个数值的、未用过的最右边。
3.将p赋值给ans[i]，记录该p已经被用过（详见代码中nxt[p]++，这样**保证下次减回来能多减一个位置**）
4.给子树预留位置。
详见代码：
```cpp
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=500000+10;
int nxt[N],a[N],ans[N],fa[N],size[N];
int n;
double k;
struct node{
int mi,l,r;
int add;
#define mix t[x].mi
#define lx t[x].l
#define rx t[x].r
#define lsx x<<1
#define rsx x<<1|1
#define ax t[x].add
#define milsx t[lsx].mi
#define mirsx t[rsx].mi
#define alsx t[x<<1].add
#define arsx t[x<<1|1].add
}t[N<<2];
void push(int x)
{
if(!ax) return;
milsx+=ax;
mirsx+=ax;
alsx+=ax;
arsx+=ax;
ax=0;
}
void build(int l,int r,int x)
{
if(l==r)
{
mix=l,lx=l,rx=r;ax=0;return;
}
int mid=(l+r)>>1;
lx=l,rx=r,ax=0;
build(l,mid,lsx);
build(mid+1,r,rsx);
mix=min(mirsx,milsx);
}
void add(int l,int r,int x,int c)
{
if(l<=lx&&rx<=r)
{
mix+=c;
ax+=c;return;
}
push(x);
int mid=(lx+rx)>>1;
if(l<=mid) add(l,r,lsx,c);
if(mid<r) add(l,r,rsx,c);
mix=min(milsx,mirsx);
}
int find(int x,int d)
{
if(lx==rx) return lx+(mix<d);
push(x);
if(mirsx<d) return find(rsx,d);
return find(lsx,d);
}
bool cmp(int a,int b) {return a>b;}
void prework()
{
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
fa[i]=int(i/k),size[i]=1;
for(int i=n-1;i;i--)
if(a[i]==a[i+1]) nxt[i]=nxt[i+1]+1;
for(int i=n;i;i--)
size[fa[i]]+=size[i];
}
int main()
{
scanf("%d%lf",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
prework();
int root=1;
build(1,n,root);
for(int i=1;i<=n;i++)
{
if(fa[i]!=fa[i-1]) add(ans[fa[i]],n,root,size[fa[i]]-1);
int p=find(root,size[i]);
p+=nxt[p];nxt[p]++;p-=nxt[p]-1;ans[i]=p;
add(p,n,root,-size[i]);
}
for(int i=1;i<=n;i++)
printf("%d ",a[ans[i]]);
return 0;
}
```