p4364 [九省联考2018]IIIDX

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

传送门

分析

我们先考虑如果所有数都不相同我们应该怎么办

我们可以直接贪心的在每个点放可行的最大权值

但是题目要求可以有相同的数

我们可以考虑每次让当前节点可发且尽量大的同时给兄弟节点留的数尽量大

我们用线段树维护每个点比它大的点还剩几个

对于每个点要给它的子树预留足够的点即可

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

int n,fa[],siz[],d[],col[];

int a[],ans[],cnt[];

double f;

inline bool cmp(const int x,const int y){return x>y;}

inline void build(int le,int ri,int wh){

    if(le==ri){

      d[wh]=le;

      return;

    }

    int mid=(le+ri)>>;

    build(le,mid,wh<<);

    build(mid+,ri,wh<<|);

    d[wh]=min(d[wh<<],d[wh<<|]);

}

inline void update(int le,int ri,int wh,int x,int y,int k){

    if(le>=x&&ri<=y){

      d[wh]+=k;

      col[wh]+=k;

      return;

    }

    int mid=(le+ri)>>;

    if(col[wh]!=){

      d[wh<<]+=col[wh];

      d[wh<<|]+=col[wh];

      col[wh<<]+=col[wh];

      col[wh<<|]+=col[wh];

      col[wh]=;

    }

    if(mid>=x)update(le,mid,wh<<,x,y,k);

    if(mid<y)update(mid+,ri,wh<<|,x,y,k);

    d[wh]=min(d[wh<<],d[wh<<|]);

}

inline int q(int le,int ri,int wh,int k){

    if(le==ri)return d[wh]>=k?le:le+;

    int mid=(le+ri)>>;

    if(col[wh]!=){

      d[wh<<]+=col[wh];

      d[wh<<|]+=col[wh];

      col[wh<<]+=col[wh];

      col[wh<<|]+=col[wh];

      col[wh]=;

    }

    if(d[wh<<|]>=k)return q(le,mid,wh<<,k);

      else return q(mid+,ri,wh<<|,k);

}

int main(){

    int i,j,k;

    scanf("%d",&n);

    cin>>f;

    for(i=;i<=n;i++)scanf("%d",&a[i]);

    for(i=;i<=n;i++)fa[i]=i/f,siz[i]=;

    sort(a+,a+n+,cmp);

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

    for(i=n-;i>;i--)cnt[i]=(a[i]==a[i+]?cnt[i+]+:);

    build(,n,);

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

      if(fa[i]&&fa[i]!=fa[i-])update(,n,,ans[fa[i]],n,siz[fa[i]]-);

      int x=q(,n,,siz[i]);

      x+=cnt[x];

      ++cnt[x];

      ans[i]=x;

      update(,n,,x,n,-siz[i]);

    }

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

    return ;

}