BZOJ5249 九省联考2018IIIDX（线段树+贪心）

时间：2025-05-01 10:37:14

　　显然这形成了一个树形结构。考虑这样一种贪心：按照曲目顺序，每次取消其父亲的预留，并选择当前可选择（保证其子树有合法选择且满足预留）的最大值，然后对其子树预留出大于等于他的一些值。这个做法显然是正确的。问题在于怎么达到预留的效果。

　　离散化后建一棵权值线段树。线段树每个节点维护这段权值其右边（即大于该权值）至少有多少个权值可以选择。预留一棵子树时，我们无法知道大于等于根的那些权值如何选择，但小于根的权值的右边的可选权值减少的个数是可以知道的。于是对于权值小于根的部分，直接把可选权值个数减掉子树大小-1。查询时在线段树上二分，看左儿子区间的右边至少有多少个权值可以选择，若该值小于需要预留的子树大小，那么就无法把子树全部塞到右边了，于是向左儿子递归，否则向右儿子递归，直到叶子节点。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 500010

int n,a[N],cnt[N],size[N],b[N],fa[N];

double k,eps=1E-;

int tree[N<<],L[N<<],R[N<<],lazy[N<<],ans[N];

void up(int k){tree[k]=min(tree[k<<],tree[k<<|]);}

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

{

    L[k]=l,R[k]=r;

    if (l==r) {tree[k]=cnt[l+];return;}

    int mid=l+r>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    up(k);

}

void down(int k)

{

    tree[k<<]+=lazy[k],tree[k<<|]+=lazy[k];

    lazy[k<<]+=lazy[k],lazy[k<<|]+=lazy[k];

    lazy[k]=;

}

void modify(int k,int l,int r,int x)

{

    if (L[k]==l&&R[k]==r){tree[k]+=x,lazy[k]+=x;return;}

    if (lazy[k]) down(k);

    int mid=L[k]+R[k]>>;

    if (r<=mid) modify(k<<,l,r,x);

    else if (l>mid) modify(k<<|,l,r,x);

    else modify(k<<,l,mid,x),modify(k<<|,mid+,r,x);

    up(k);

}

int query(int k,int x)

{

    if (L[k]==R[k]) return L[k];

    if (lazy[k]) down(k);

    int mid=L[k]+R[k]>>,ans;

    if (tree[k<<]<x) ans=query(k<<,x);

    else ans=query(k<<|,x);

    up(k);return ans;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5249.in","r",stdin);

    freopen("bzoj5249.out","w",stdout);

    const char LL[]="%I64d";

#else

    const char LL[]="%lld";

#endif

    n=read();cin>>k;

    for (int i=;i<=n;i++) b[i]=a[i]=read();

    sort(b+,b+n+);

    int t=unique(b+,b+n+)-b-;

    for (int i=;i<=n;i++) a[i]=lower_bound(b+,b+t+,a[i])-b;

    sort(a+,a+n+);

    for (int i=;i<=n;i++) if (a[i]!=a[i-]) cnt[a[i]]=n-i+;

    build(,,t);

    for (int i=;i<=n;i++) fa[i]=(double)i/k+eps,size[i]=;

    for (int i=n;i>=;i--) size[fa[i]]+=size[i];

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

    {

        if (fa[i]!=fa[i-]) modify(,,ans[fa[i]]-,size[fa[i]]-);

        ans[i]=query(,size[i]);

        modify(,,ans[i]-,-size[i]);

    }

    for (int i=;i<=n;i++) printf("%d ",b[ans[i]]);

    return ;

}

相关文章