自动搬运

查看原文

来自洛谷，原作者为

	Sakits **

搬运于2025-08-24 21:59:24，当前版本为作者最后更新于2018-04-07 19:43:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

https://sakits.com/bzoj5249/

题解

显然题意可以抽象成：一棵树，要对树上的每个点标上给定的权值，满足每个点上的权值都$\leq$子树内点的权值，并使这个棵树编号从小到大的权值字典序最大。

首先可以一眼得到一个做法，将权值从大到小排序，把长度为子树大小的一段按子树编号从小到大丢给它们，递归下去得到答案。

这种做法在$d_i$不重复的时候是正确的，那$d_i$要是有相同的数呢？

有可能可以将编号$x$子树里一个大的权值与编号$x+1$的子树根的权值替换，使得$x$的权值依然是能取得的最大数且子树内的数都比$x$的权值大，同时$x+1$子树内的点也还能标满$\geq$$x+1$权值的权值。

那怎么做呢？先把给定权值从大到小排序，线段树上维护每个权值左边（包括本身）还能取的权值的个数$C_i$。

当取好一个点$x$的权值时，需要给它子树内的点预留取的权值，这些权值显然在$x$取得权值的左边，但是我们并不知道取的是哪些权值，所以只把$x$取得的权值右边（包括本身）的$C_i$减去$x$子树大小$size[x]$，每次取一个点$y$的权值时，只需要在线段树上找到最大权值$val$满足$val$所在位置右边（包括本身）的所有$C_i\geq size[y]$，且$val$尽可能靠右即可，这个在线段树上二分就能做到。

如果一个点有父亲，求它的权值时要把它父亲为子树预留的大小去掉，需要注意的是，每个父亲预留的大小只要去掉一次，写的时候容易忽略这一点，WA了半天T_T。

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int mn, delta;}tree[maxn<<2];
int n, N;
double k;
int a[maxn], b[maxn], ans[maxn], size[maxn], fa[maxn], cnt[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline bool cmp(int a, int b){return a>b;}
inline void addone(int x, int delta){tree[x].delta+=delta; tree[x].mn+=delta;}
inline void up(int x){tree[x].mn=min(tree[x<<1].mn, tree[x<<1|1].mn);}
inline void down(int x)
{
	addone(x<<1, tree[x].delta);
	addone(x<<1|1, tree[x].delta);
	tree[x].delta=0;
}
void build(int x, int l, int r)
{
	if(l==r){tree[x].mn=l; return;}
	int mid=(l+r)>>1;
	build(x<<1, l, mid); build(x<<1|1, mid+1, r);
	up(x);
}
int query(int x, int l, int r, int k)
{
	if(l==r) return (tree[x].mn>=k?l:l+1);
	down(x);
	int mid=(l+r)>>1;
	if(k<=tree[x<<1|1].mn) return query(x<<1, l, mid, k);
	else return query(x<<1|1, mid+1, r, k);
}
void update(int x, int l, int r, int cl, int cr, int delta)
{
	if(cl<=l && r<=cr){tree[x].mn+=delta; tree[x].delta+=delta; return;}
	down(x);
	int mid=(l+r)>>1;
	if(cl<=mid) update(x<<1, l, mid, cl, cr, delta);
	if(cr>mid) update(x<<1|1, mid+1, r, cl, cr, delta);
	up(x);
}
int main()
{
	read(n); scanf("%lf", &k);	
	for(int i=1;i<=n;i++) read(a[i]);
	sort(a+1, a+1+n, cmp);
	for(int i=n-1;i;i--) 
	if(a[i]==a[i+1]) cnt[i]=cnt[i+1]+1; else cnt[i]=0;
	for(int i=1;i<=n;i++) fa[i]=(int)floor(i/k), size[i]=1;
	for(int i=n;i;i--) size[fa[i]]+=size[i];
	build(1, 1, n);
	for(int i=1;i<=n;i++)
	{
		if(fa[i]&&fa[i]!=fa[i-1]) update(1, 1, n, ans[fa[i]], n, size[fa[i]]-1);
		int x=query(1, 1, n, size[i]); 
		x+=cnt[x]; cnt[x]++; x-=(cnt[x]-1); ans[i]=x; 
		update(1, 1, n, x, n, -size[i]);
	}
	for(int i=1;i<=n;i++) printf("%d ", a[ans[i]]);
}