5249: [2018多省省队联测]IIIDX

链接

分析：

　　贪心。

　　将给定的权值从大到小排序，从第一个往后挨个赋值，考虑第i个位置可以赋值那些树。首先满足前面必须至少有siz[i]个权值没选，如果存在相同的数，尽量往后选。

　　那么可以给每个权值记录一个值F[i]，表示i左边可以选多少个权值了。还要和后面的取一个最小值才是真正的能选多少个。

　　在线段树上分治找到这个位置。

　　注意在bzoj上，fa[i]=int(1.0*i/k) 有精度误差，而写成floor就可以了。

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

#define lson l, mid, rt << 1

#define rson mid + 1, r, rt << 1 | 1

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int Mn[N << ], tag[N << ], R[N], fa[N], siz[N], ans[N], cnt[N], w[N];

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

inline void pushup(int rt) { Mn[rt] = min(Mn[rt << ], Mn[rt <<  | ]); }

inline void pushdown(int rt) {

    tag[rt << ] += tag[rt];tag[rt <<  | ] += tag[rt];

    Mn[rt << ] += tag[rt];Mn[rt <<  | ] += tag[rt];

    tag[rt] = ;

}

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

    tag[rt] = ;

    if (l == r) {

        Mn[rt] = l; return ;

    }

    int mid = (l + r) >> ;

    build(lson); build(rson);

    pushup(rt);

}

void update(int l,int r,int rt,int L,int R,int v) {

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

        tag[rt] += v; Mn[rt] += v; return ;

    }

    if (tag[rt]) pushdown(rt);

    int mid = (l + r) >> ;

    if (L <= mid) update(lson, L, R, v);

    if (R > mid) update(rson, L, R, v);

    pushup(rt);

}

int query(int l,int r,int rt,int x) {

    if (l == r) return l + (Mn[rt] < x);

    if (tag[rt]) pushdown(rt);

    int mid = (l + r) >> ;

    if (x <= Mn[rt <<  | ]) return query(lson, x);

    else return query(rson, x);

}

int main() {

    int n = read();

    double k; scanf("%lf", &k);

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

        fa[i] = floor(1.0 * i / k), siz[i] ++, siz[fa[i]] += siz[i];

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

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

    build(, n, );

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

        if (w[i] == w[i + ]) R[i] = R[i + ];

        else R[i] = i;

    }

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

        if (fa[i] && fa[i] != fa[i - ])

            update(, n, , ans[fa[i]], n, siz[fa[i]] - );

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

        x = R[x]; cnt[x] ++; x -= cnt[x] - ; ans[i] = x;

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

    }

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

    return ;

}