IIIDX[九省联考2018]

发表于 分类于 ， ，

题目链接

loj

题意

一棵树，$i$ 的父亲是 $\left\lfloor \frac{i}{k}\right\rfloor$ 一个乱序的数组 $d$，大小均为 $n$。将数组中的数扔进树中的点做点权，使得 $d_i\geq d_{fa_i}$。输出满足条件的最大字典序。

$n\leq 5\times 10^5$。

题解

如果 $d_i$ 互不相同，那么对于相同层数的点从小到大贪心一下即可。50pts。

但是如果 $d_i$ 有相同的，因为可以有等于的限制，所以上面的贪心就行不通了。

考虑换一种贪心，对于一棵子树 $u$，我们需要选择最大 $d_i$ 满足剩下的还能选择的 $d$ 中至少有 $siz_u$ 个。那也就是将 $d_i$ 从大到小排序，设 $f_i$ 表示还剩下 $f_i$ 个大于等于 $d_i$ 的 $d$ 可以选择，初始时 $f_i=i$。对于子树 $u$ 而言，需要找到最小的 $i$ 满足 $f_i\geq siz_u$，但是这个 $i$ 并不一定是最优的，显然最优的是最大的 $j$ 满足 $d_i=d_j$（实际上就是把所有的 $d_i$ 相同的搞到一起考虑）。然后将 $f[j,n]$ 都减去 $siz_u$，表示我会先预留 $siz_u$ 个位置给子树 $u$ 中的所有点。然后继续处理 $u+1$。

需要用的操作是区间加，查询第一个大于某个值的下标。这个用线段树即可实现。

需要注意的是处理到 $u$ 时，需要把 $fa_u$ 预留的位置所做的贡献删掉。

时间复杂度 $O(n\log n)$。

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=500010;
int n; db k;
#define lc (u<<1)
#define rc (u<<1|1)
#define ls lc,l,mid
#define rs rc,mid+1,r
int mi[N<<2],tag[N<<2];
inline void pushtag(int u,int d)
{
	mi[u]+=d; tag[u]+=d;
}
inline void pushdown(int u)
{
	if(tag[u]==0) return;
	pushtag(lc,tag[u]); pushtag(rc,tag[u]);
	tag[u]=0;
}
void build(int u,int l,int r)
{
	if(l==r) {mi[u]=l,tag[u]=0; return;}
	int mid=l+r>>1;
	build(ls); build(rs);
	mi[u]=min(mi[lc],mi[rc]);
}
void add(int u,int l,int r,int L,int R,int d)
{
	if(L<=l&&r<=R) return pushtag(u,d);
	pushdown(u);
	int mid=l+r>>1;
	if(L<=mid) add(ls,L,R,d);
	if(mid<R)  add(rs,L,R,d);
	mi[u]=min(mi[lc],mi[rc]);
}
int ask(int u,int l,int r,int d)
{
	if(l==r) return mi[u]>=d?l:l+1;
	pushdown(u);
	int mid=l+r>>1;
	return d<=mi[rc]?ask(ls,d):ask(rs,d); 
}
bool bo[N];
int fa[N],d[N],siz[N],las[N],ans[N];
int main()
{
	n=read(); scanf("%lf",&k);
	fo(i,1,n) d[i]=read();
	sort(d+1,d+n+1,[&](const int &x,const int &y){return x>y;});
	fd(i,n,1)
	{
		fa[i]=1.*i/k;
		++siz[i];
		siz[fa[i]]+=siz[i];
		las[i]=i;
		if(i!=n&&d[i]==d[i+1]) las[i]=las[i+1];
	}
	build(1,1,n);
	fo(i,1,n)
	{
		int u=fa[i];
		if(u&&!bo[u]) bo[u]=1,add(1,1,n,ans[u],n,siz[u]-1);
		ans[i]=las[ask(1,1,n,siz[i])];
		add(1,1,n,ans[i],n,-siz[i]);
		printf("%d ",d[ans[i]]);
	}
	return 0;
}