SDOI2018IIIDX

/*

题目转换为  n个节点的一片森林，n个权值，要给每个节点分配一个权值，保证子节点的权值不小于父节点的权值，并且1~n的权值的字典序最大。

考场上的贪心很显然  建立出 树来  将所有数值从大到小排序 然后后序遍历依次填进去  这样就可以处理 互不相同的数据  然后一旦有相同的就会gg

正解

考虑从前往后贪心  我们把所有的数字按照从大到小排序， 然后从前往后贪心

每个位置贪心找当前能放的最大的，也就是保证子树元素都比改点大， 如果有相同的， 令我们选择在序列中最靠右的，这样才有可能将较大的留给后面的

 对于数列构建线段树  令res[i] 表示第i个元素以及他左边 空余的元素有多少个  每次查询在线段树上二分

 找到这个元素之后 体会一下他的所有孩子都会比这个元素大  所以res[i - n] 都要减去sz[i]

 这个限制 当我们遍历该节点的第一个孩子时  将其去除即可

*/

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<iostream>

#define M 500010

#define fa(x) (int) floor((x) / (k))

#define inf 1000000000

using namespace std;

int read() {

    int nm = , f = ;

    char c = getchar();

    for(; !isdigit(c); c = getchar()) if(c == '-') f = -;

    for(; isdigit(c); c  =getchar() ) nm = nm *  + c - '';

    return nm * f;

}

int n, res[M << ], lazy[M << ], note[M], b[M], sz[M], ans[M], cnt[M];

double k;

void pushup(int now) {

    res[now] = min(res[now << ], res[now <<  | ]);

}

void pushdown(int now) {

    if(!lazy[now]) return;

    lazy[now << ] += lazy[now], res[now << ] += lazy[now], lazy[now <<  | ] += lazy[now], res[now <<  | ] += lazy[now];

    lazy[now] = ;

}

void build(int l, int r, int now) {

    if(l > r) return;

    if(l == r) {

        res[now] = l;

        return;

    }

    int mid = (l + r) >> ;

    build(l, mid, now << );

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

    pushup(now);

}

void modify(int l, int r, int now, int ln, int rn, int ver) {

    if(l > rn || r < ln) return ;

    if(l >= ln && r <= rn) {

        res[now] += ver;

        lazy[now] += ver;

        return;

    }

    int mid = (l + r) >> ;

    pushdown(now);

    modify(l, mid, now << , ln, rn , ver);

    modify(mid + , r, now <<  | , ln, rn,ver);

    pushup(now);

}

int query(int l, int r, int now, int k) {

    if(l == r) return (res[now] >= k) ?l : l + ;

    int mid = (l + r) >> ;

    pushdown(now);

    if(k <= res[now <<  | ]) return query(l, mid ,now << , k);

    return query(mid + , r, now <<  | , k);

}

int main() {

    n = read();

    cin >> k;

    for(int i = ; i <= n; i++) note[i] = read(), sz[i] = ;

    sort(note + , note + n + , greater<int>() );

    for(int i = n; i >= ; i--) {

        if(note[i] == note[i + ]) cnt[i] = cnt[i + ] + ;

        else cnt[i] = ;

        sz[fa(i)] += sz[i];

    }

    build(, n, );

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

        if(fa(i) && fa(i) != fa(i - )) modify(, n, , ans[fa(i)], n, sz[fa(i)] - );

        int op = query(, n, , sz[i]);

        op += cnt[op],cnt[op]++,op -= (cnt[op] - ),ans[i] = op;

        modify(, n, , op, n, -sz[i]);

    }

    for(int i = ; i <= n; i++) cout << note[ans[i]] << " ";

    return ;

}