bzoj5249:[2018多省省队联测]IIIDX(线段树)

Author Avatar
Sakits 4月 07, 2018

题解

  显然题意可以抽象成:一棵树,要对树上的每个点标上给定的权值,满足每个点上的权值都\leq子树内点的权值,并使这个棵树编号从小到大的权值字典序最大。
  首先可以一眼得到一个做法,将权值从大到小排序,把长度为子树大小的一段按子树编号从小到大丢给它们,递归下去得到答案。
  这种做法在did_i不重复的时候是正确的,那did_i要是有相同的数呢?
  有可能可以将编号xx子树里一个大的权值与编号x+1x+1的子树根的权值替换,使得xx的权值依然是能取得的最大数且子树内的数都比xx的权值大,同时x+1x+1子树内的点也还能标满\geqx+1x+1权值的权值。
  那怎么做呢?先把给定权值从大到小排序,线段树上维护每个权值左边(包括本身)还能取的权值的个数CiC_i
  当取好一个点xx的权值时,需要给它子树内的点预留取的权值,这些权值显然在xx取得权值的左边,但是我们并不知道取的是哪些权值,所以只把xx取得的权值右边(包括本身)的CiC_i减去xx子树大小size[x]size[x],每次取一个点yy的权值时,只需要在线段树上找到最大权值valval满足valval所在位置右边(包括本身)的所有Cisize[y]C_i\geq size[y],且valval尽可能靠右即可,这个在线段树上二分就能做到。
  如果一个点有父亲,求它的权值时要把它父亲为子树预留的大小去掉,需要注意的是,每个父亲预留的大小只要去掉一次,写的时候容易忽略这一点,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]]);
}