【luoguP4364】 [九省联考2018]IIIDX

这个题目当初我考场就是个智障,连55的贪心都没做对qwq
首先一个比较显然的思路,我们先建树,\(\lfloor{\frac{i}{k}}\rfloor\)即为\(i\)的父亲,然后我们从大到小排个序,按照中序遍历给他赋值
但是这样的贪心在\(d_{i}\)重复的时候就gg了,因为我们发现可以用子树内部较大的值去换掉其他子树上比较小的值,因此我们要换个思路贪心
我们还是排序,每次去寻找一个可以容纳的下子树大小的区间,比如9 9 9 8 7 7 6 6 6 5,这个时候我们要插入一棵大小为7的子树。这个时候我们很显然会找到第7个数——6。然后我们再一直移动到第九个数——还是6。这是为了保证和我同一层的子树根尽可能的大,所以在我这棵子树的根并不会变小的时候,我多留点空为后面的子树。
这个时候我们为了防止别的树占用我们的预定好了的区间,所以我们需要设置一个辅助数组。设mi[i]表示权值大于等于i的数还有多少是可以选择的,那么排序过后mi[i]就可以转化为i左边还剩下多少数字可以使用。这个东西显然是满足单调不降的。那么我们就可以线段树去维护,每次预定的时候就区间减法
然而大多数人都选择了将减法变为加法,将被选取的区间和整个一段取了个补集,让他们进行区间加。这也就是为什么网上这么多题解嘴上都在说减法实际上一个减法都没有的原因。
每次变更父亲的时候提前钦定一波,每个子树选完了就再减回去。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = (x << 1) + (x << 3) + a - '0', a = getchar();
    if(b == 1)
        x *= -1;
}

const int ms = 5e5 + 10;

int n, a[ms], fa[ms], sz[ms], cnt[ms], pos[ms];

struct in
{
    int l, r, mi, add;
}ter[ms << 2];

double k;

inline bool cmp(int a, int b)
{
    return a > b;
}

inline void up(int w)
{
    ter[w].mi = min(ter[w << 1].mi, ter[w << 1 | 1].mi);
}

inline void build(int w, int l, int r)
{
    ter[w] = (in){l, r, l};
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(w << 1, l, mid), build(w << 1 | 1, mid + 1, r);
}

inline void down(int w)
{
    int &add = ter[w].add;
    ter[w << 1].add += add, ter[w << 1 | 1].add += add;
    ter[w << 1].mi += add, ter[w << 1 | 1].mi += add;
    add = 0;
}

void change(int w, int l, int r, int v)
{
    if(ter[w].l == l && ter[w].r == r)
    {
        ter[w].mi += v, ter[w].add += v; return;
    }
    int mid = (ter[w].l + ter[w].r) >> 1; down(w);
    if(r <= mid)
        change(w << 1, l, r, v);
    else if(l > mid)
        change(w << 1 | 1, l, r, v);
    else
        change(w << 1, l, mid, v), change(w << 1 | 1, mid + 1, r, v);
    up(w);
}

int ask(int w, int l)
{
    if(ter[w].l == ter[w].r)
        return ter[w].mi >= l ? ter[w].l : ter[w].l + 1;
    int mid = (ter[w].l + ter[w].r) >> 1; down(w);
    if(ter[w << 1 | 1].mi >= l)
        return ask(w << 1, l);
    return ask(w << 1 | 1, l);
}

int main()
{
    re(n), scanf("%lf", &k);
    for(ri i = 1; i <= n; fa[i] = (int)i / k, sz[i] = 1, re(a[i ++]));
    sort(a + 1, a + 1 + n, cmp);
    for(ri i = n; i >= 1; i --)
        sz[fa[i]] += sz[i];
    for(ri i = n - 1; i >= 0; i --)
        cnt[i] = (a[i] == a[i + 1]) ? cnt[i + 1] + 1 : 0;
    build(1, 1, n);
    for(ri i = 1; i <= n; i ++)
    {
        if(fa[i] && fa[i - 1] != fa[i])
            change(1, pos[fa[i]], n, sz[fa[i]] - 1);
        int x = ask(1, sz[i]);  x += cnt[x], cnt[x] ++, x -= (cnt[x] - 1);
        change(1, x, n, - sz[i]), pos[i] = x;
    }
    for(ri i = 1; i <= n; printf("%d ", a[pos[i ++]]));
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注