bzoj5249 [2018多省省隊聯測]IIIDX

​​http://www.elijahqi.win/archives/3012​​​

Description

【題目背景】

Osu聽過沒？那是Konano最喜歡的一款音樂遊戲，而他的夢想就是有一天自己也能做個獨特酷炫的音樂遊戲。現在

，他在世界知名遊戲公司KONMAI内工作，離他的夢想也越來越近了。這款音樂遊戲内一般都包含了許多歌曲，歌曲

越多，玩家越不易玩膩。同時，為了使玩家在遊戲上氪更多的金錢花更多的時間，遊戲一開始一般都不會将所有曲

目公開，有些曲目你需要通關某首特定歌曲才會解鎖，而且越晚解鎖的曲目難度越高。

【題目描述】

這一天，Konano接到了一個任務，他需要給正在制作中的遊戲《IIIDX》安排曲目的解鎖順序。遊戲内共有n首曲目

，每首曲目都會有一個難度d，遊戲内第i首曲目會在玩家Pass第trunc(i/k)首曲目後解鎖（x為下取整符号）若tru

nc(i/k)=0，則說明這首曲目無需解鎖。舉個例子：當k=2時，第1首曲目是無需解鎖的（trunc(1/2)=0），第7首曲

目需要玩家Pass第trunc(7/2)=3首曲目才會被解鎖。Konano的工作，便是安排這些曲目的順序，使得每次解鎖出的

曲子的難度不低于作為條件需要玩家通關的曲子的難度，即使得确定順序後的曲目的難度對于每個i滿足Di≥Dtrun

c(i/k)。當然這難不倒曾經在資訊學競賽摸魚許久的Konano。那假如是你，你會怎麼解決這份任務呢

Input

第1行1個正整數n和1個小數k，n表示曲目數量，k其含義如題所示。

第2行n個用空格隔開的正整數d，表示這n首曲目的難度。

1 ≤ n ≤ 500000

1 < k ≤ 10^9

1 < d ≤ 10^9

Output

輸出1行n個整數，按順序輸出安排完曲目順序後第i首曲目的難度。

若有多解，則輸出d1最大的；若仍有多解，則輸出d2最大的，以此類推。

Sample Input

#include<cstdio>
#include<cctype>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define eps 1e-8
using namespace std;
const int N=500050;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct node{int mn,tag;}tree[N<<2];
inline void update(int x){tree[x].mn=min(tree[lc].mn,tree[rc].mn);}
inline void build(int x,int l,int r){
    if (l==r) {tree[x].mn=l;return;}int mid=l+r>>1;
    build(lc,l,mid);build(rc,mid+1,r);update(x);
}
inline void pushdown(int x){
    if (!tree[x].tag) return;static int tag;
    tag=tree[x].tag;tree[x].tag=0;
    tree[lc].mn+=tag;tree[lc].tag+=tag;
    tree[rc].mn+=tag;tree[rc].tag+=tag;
}
inline void modify(int x,int l,int r,int l1,int r1,int v){
    if (l1<=l&&r1>=r){tree[x].mn+=v;tree[x].tag+=v;return;}
    int mid=l+r>>1;pushdown(x);
    if (l1<=mid) modify(lc,l,mid,l1,r1,v);
    if (r1>mid) modify(rc,mid+1,r,l1,r1,v);update(x);
}
inline int query(int x,int l,int r,int p){
    if (l==r) return tree[x].mn>=p?l:l+1;int mid=l+r>>1;pushdown(x);
    if(p<=tree[rc].mn) return query(lc,l,mid,p);else return query(rc,mid+1,r,p);
}
inline bool cmp(const int &a,const int &b){return a>b;}
int n,d[N],size[N],cnt[N],fa[N],ans[N];double k; 
int main(){
    freopen("bzoj5249.in","r",stdin);
    n=read();scanf("%lf",&k);
    for (int i=n;i;--i) d[i]=read(),fa[i]=i/k+eps,++size[i],size[fa[i]]+=size[i];
    sort(d+1,d+n+1,cmp);build(1,1,n);
    for (int i=n-1;i;--i) if (d[i]==d[i+1]) cnt[i]=cnt[i+1]+1;
    for (int i=1;i<=n;++i){
        if(fa[i]&&fa[i-1]!=fa[i]) modify(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;modify(1,1,n,x,n,-size[i]);
    }for (int i=1;i<=n;++i) printf("%d ",d[ans[i]]);
    return 0;
}