「九省联考 2018」IIIDX 解题报告

时间：2023-03-08 19:27:08

「九省联考 2018」IIIDX

这什么鬼题，送的55分要拿稳，实测有60？

考虑把数值从大到小摆好，每个位置\(i\)维护一个\(f_i\)，表示\(i\)左边比它大的（包括自己）还有几个数可以选

这个最开始直接处理好，就是>=数值\(i\)的数字个数

如果我们从小到大安排，发现我们需要给当前数安排一个数值，根据贪心，这个数值要尽可能大，但又要满足一个条件，就是这个数值右边的\(\min \{f_i\}\ge siz_{now}\)

安排完了以后，需要给子树再安排一下，就把右边区间的\(f_i\)做一个区间减

然后注意一个事情，进入子树以后，子树会去安排子树，所以在进子树第一个点后要把父亲的安排撤回。

感性一点理解的说，就是贪心的选一个可以选的最大值，需要保证还有一定数目的更大值可以在后面被选，但是你不知道到底这个后面的最大值怎么被选了，于是先维护好已经被选了一定个数这个信息，后面再去安排它。你现在安排它是为了排在它后面的同层点不去干扰它们

Code:

#include <cstdio>

#include <algorithm>

using std::min;

const int N=5e5+10;

const double eps=1e-6;

int n,d[N],b[N],par[N],pos[N],yuu[N],siz[N];

double k;

#define ls id<<1

#define rs id<<1|1

int mi[N<<2],tag[N<<2];

void build(int id,int l,int r)

{

	if(l==r) {mi[id]=yuu[l];return;}

	int mid=l+r>>1;

	build(ls,l,mid),build(rs,mid+1,r);

	mi[id]=min(mi[ls],mi[rs]);

}

void pushdown(int id)

{

	if(tag[id])

	{

		mi[ls]+=tag[id];

		mi[rs]+=tag[id];

		tag[ls]+=tag[id];

		tag[rs]+=tag[id];

		tag[id]=0;

	}

}

void ins(int id,int L,int R,int l,int r,int d)

{

	if(l==L&&r==R)

	{

		mi[id]+=d;

		tag[id]+=d;

		return;

	}

	pushdown(id);

	int Mid=L+R>>1;

	if(r<=Mid) ins(ls,L,Mid,l,r,d);

	else if(l>Mid) ins(rs,Mid+1,R,l,r,d);

	else ins(ls,L,Mid,l,Mid,d),ins(rs,Mid+1,R,Mid+1,r,d);

	mi[id]=min(mi[ls],mi[rs]);

}

int query(int id,int l,int r,int s)

{

	if(l==r) return mi[id]>=s?l:l+1;

	pushdown(id);

	int mid=l+r>>1;

	if(mi[rs]>=s) return query(ls,l,mid,s);

	else return query(rs,mid+1,r,s);

}

int main()

{

	scanf("%d%lf",&n,&k);

	for(int i=1;i<=n;i++) scanf("%d",d+i),par[i]=1.0*i/k+eps;

	std::sort(d+1,d+1+n);

	int m=0,p=1;b[p]=d[n];

	for(int i=1;i<=n;i++) if(d[i]!=d[i-1]) ++m;

	for(int i=n-1;~i;i--)

		if(d[i]!=d[i+1])

		{

			yuu[p]=n-i;

			b[++p]=d[i];

		}

	build(1,1,m);

	for(int i=n;i;i--) ++siz[i],siz[par[i]]+=siz[i];

	for(int i=1;i<=n;i++)

	{

		if(par[i]&&par[i]!=par[i-1]) ins(1,1,m,pos[par[i]],m,siz[par[i]]-1);

		pos[i]=query(1,1,m,siz[i]);

		printf("%d ",b[pos[i]]);

		ins(1,1,m,pos[i],m,-siz[i]);

	}

	return 0;

}

2019.3.18

相关文章