Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4364 [九省联考 2018] IIIDX

Posted on In
Symbols count in article: 2k Reading time ≈ 2 mins.

细节很多

IIIDX

思路

发现就是给一个森林排权值，要求浅的（编号小的）尽量大，且儿子都大于等于父亲，没有重复数的时候直接贪心即可，考虑有重复，此时贪心挂了，如：

1
2
4 2.0
1 1 1 2

答案是：

1
1 1 2 1

不妨先给权值排序，考虑用线段树维护“每个点右边可选的点还有几个”（不妨记做 $mn[]$ ），对于当前点，若它的子树大小为 $si$ ，那么就要在保证它左边所有点的 $mn[] \ge si$ 的前提下尽可能往右（大），然后让它所选节点的左边（包括自己）的 $mn$ 减 $si$ 来为它的子树预留数，而当真正进到它的子树时在把预留的数加回来， 本题有一个很好的性质：它的儿子编号都是连续的，所以在扫到第一个儿子时加即可

需要注意的是，若有多个相同的数，应取最左的，这可以二分实现；以及线段树上二分时最后取的点可能并不满足条件，此时应该取它左边的点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
const int N = 5e5 + 100;
using namespace std;
int n, si[N], fa[N], d[N], ans[N];
bool used[N];
namespace LT
{
    int mn[N << 2], tg[N << 2];
    #define lc (u << 1)
    #define rc ((u << 1) | 1)
    #define mid ((l + r) >> 1)
    void bd(int u = 1, int l = 1, int r = n)
    {
        mn[u] = n - r + 1, tg[u] = 0;
        if (l < r) bd(lc, l, mid), bd(rc, mid + 1, r);
    }
    void up(int u){ mn[u] = std::min(mn[lc], mn[rc]); }
    void adt(int u, int d){ mn[u] += d, tg[u] += d; }
    void dn(int u)
    {
        if (tg[u])
        {
            adt(lc, tg[u]), adt(rc, tg[u]);
            tg[u] = 0;
        }
    }
    void mdf(int ql, int qr, int d, int u = 1, int l = 1, int r = n)
    {
        if (l >= ql && r <= qr) return adt(u, d);
        dn(u);
        if (ql <= mid) mdf(ql, qr, d, lc, l, mid);
        if (qr > mid) mdf(ql, qr, d, rc, mid + 1, r);
        up(u);
    }
    int ask(int x, int u = 1, int l = 1, int r = n)
    { 
        if (l == r) return (mn[u] >= x) ? l : (l - 1);
        dn(u);
        return (x <= mn[lc]) ? ask(x, rc, mid + 1, r) : ask(x, lc, l, mid);
    }
    #undef lc
    #undef rc
    #undef mid
}
int find(int x)
{
    int l = 1, r = x, mid, res = x;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (d[mid] == d[x] && !used[mid]) res = mid, r = mid - 1;
        else l = mid + 1;
    }
    return res;
}
int main()
{
    double k;
    scanf("%d %lf", &n, &k);
    for (int i = 1; i <= n; ++i) scanf("%d", &d[i]);
    for (int i = 1; i <= n; ++i) fa[i] = std::floor(i / k);
    std::fill(si + 1, si + n + 1, 1);
    for (int i = n; i; --i) si[fa[i]] += si[i];
    std::sort(d + 1, d + n + 1), LT::bd();
    for (int i = 1; i <= n; ++i)
    {
        if (fa[i] && fa[i] != fa[i - 1]) LT::mdf(1, ans[fa[i]], si[fa[i]] - 1);
        int id = LT::ask(si[i]);
        id = find(id);
        ans[i] = id, used[id] = true;
        LT::mdf(1, id, -si[i]);
    }
    for (int i = 1; i <= n; ++i) printf("%d ", d[ans[i]]);
    return 0;
}