<题解>P4364[九省联考2018]IIIDX

P4364 九省联考2018 IIIDX

题意:n个摆成一根直线的盒子,有依赖关系(连续的盒子的父亲是一个盒子),你有n个带编号的球(编号可能相同),要放在盒子里面,要求一个盒子的编号要大于其父亲的编号,并且要求序列顺序下前面的值尽量大

先考虑球两两不同的情况:我们先按权值大小从大到小排序,然后从序列顺序依次考虑每棵子树,如:

5 4 3 2 1

1的子树大小为3,那么我们就拿出5 4 3为第一棵子树,类推即可

接下来我们考虑为什么这样做是错的:

3 3 2 2 1

a       b
|\      |
c d     e

假如还是3个点,我们取了3 3 2,发现不是最优的,正确的方法是3 2 2,然后第二个子树是3 1

我们来考虑维护两个东西:

  1. f_i表示从大到小第i个球前面有多少个球(至少现在是这个意思),那么初始化就是f_i=i
  2. g_i表示从大到小第i个球到后面有多少个球和自己一样(不含自己),如上面的那个序列就是1 0 1 0 0

接下来我们查询放x=3个球的最大是哪个球,发现是第三个球,但是g_3 = 1,于是我们在第四位及其以后每一位f_i = f_i -3代表[1, 4]3个球被占用,序列变成1 2 3 1 2,这个时候你就发现f的意思不大一样了...
新的序列我们可以考虑为这样:如果存在一个j > i使f_i > f_j,那么就说明f_i已经被锁定了。(我们锁f_i大的方便我们取f_i小的,也就是编号大的)

接下来我们要取两个球,因为球的编号要尽量大,所以我们取尽量左边的球,我们发现第二位的2,但是第二位右边有个1,说明那个2是不能取的(1~4只有一个球是空闲的!取了这里面的2,那子树就没有球了!),我们就找到第二个2,然后f_i=f_i-2\quad i\ge 5预留2个球,序列变成1 2 3 1 0,最右边有个0,说明我们这个序列没有球了。

接下来看c盒子,由于父亲a留了2个球给他的儿子,我们现在对留给我们的球解锁,把父亲减数的点加size_a - 1,序列变成1 2 3 3 2,然后取1个点出来,...

我们再总结一下:

a = [3 3 2 2 1]
f = [1 2 3 4 5]
g = [1 0 1 0 0]

size[1] = 3
f[x]?v=3 -> x = 3
x += g[x] -> x = 4
f[4...] -= 3 -> [1 2 3 1 2]
ans[1] = x -> 4 (a[4] = 2)

size[2] = 2
f[x]?v=2 -> x = 2
\because f[4] = 1
\therefore f[x]?v=2&&x>4 -> x = 5
x += g[5] -> x = 5
f[5...] -= 2 -> [1 2 3 1 0]

size[3] = 1
fa[3] = 1
vis[fa[3]] == false
\therefore f[ans[1]...] += size[ans[1] - 1]
    ->[1 2 3 3 4]
f[x]?v=1 -> x = 1
x += g[x] -> x = 2
f[2...] -= 1 -> [1 1 2 2 3]

可能你看完还是迷迷糊糊的,我们回过头来看这个“f”序列:

  1. 意思还是“从大到小第i个球前面有多少个”
  2. 排好序以后一段连续的球我们考虑在最右的那个球打标记,考虑这个情况:
3 3 2 2 1
a     b     c
|\
c d

我们在尽可能在右边的地方打标记,方便后面(可以的话)取更左边的球

3 3 0 2 1 -> b没法取第一个球
3 3 2 1 1

然后我们看相同球序列最右边和非最右边的区别

1 2 2 2 3
1 2 3 4 5
1. 我们不管取第二第三个,最后都是在第四个球处加加减减
2. 最后加加减减3次以后,f_4=1,能够代表整段2不能选了

3. 对f_x减一个数之后,f_i > f_xi < x的球将在f_x解锁之后继续保持作用(不再可能保持就代表那个球被选了),而相同球序列最右边的f用了一次以后就肯定不会再次选了(想想为什么),所以f序列是有效的

对f使用线段树维护,参见代码:

void update(int p)
{
    P = std::min(L, R);
}
void pushdown(int p)
{
    if (t[p])
    {
        L += t[p];
        R += t[p];
        t[LV] += t[p];
        t[RV] += t[p];
        t[p] = 0;
    }
}

void add(int p, int l, int r)
{
    if (pl <= l && r <= pr)
    {
        P += pv;
        t[p] += pv;
        return;
    }
    pushdown(p);
    int mid = (l + r) >> 1;
    if (pl <= mid) add(LV, l, mid);
    if (mid < pr) add(RV, mid + 1, r);
    update(p);
}

int get(int p, int l, int r)
{
    if (l == r) return P >= px ? l : l + 1;
    //上面那个三元表达式:考虑1 1 2 3取2
    pushdown(p);
    if (px > R) //说明不能选左边的序列
        return get(RV, ((l + r) >> 1) + 1, r);
    else
        return get(LV, l, (l + r) >> 1);
}
signed main(void)
{
    scanf("%d %lf", &n, &k);
    for (int i = 1; i <= n; ++i) a[i] = read;
    std::sort(a + 1, a + n + 1, std::greater<int>());
    Seg::build(1, 1, n);
    for (int i = n; i; --i)
    {
        size[i] += 1;
        size[FA(i)] += size[i];
        ptr[i] = a[i] == a[i + 1] ? ptr[i + 1] + 1 : 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        static bool vis[N];
        static int fa;
        fa = FA(i);
        if (fa && !vis[fa])
        {
            Seg::add(ans[fa], size[fa] - 1);
            vis[fa] = true;
        }
        int tg = Seg::get(size[i]);
        tg += ptr[tg];
        ans[i] = tg;
        Seg::add(tg, -size[i]);
    }
    for (int i = 1; i <= n; ++i) printf("%d ", a[ans[i]]);
}

附赠完整代码:

#include <bits/stdc++.h>

struct Read
{
    //...
} read;

const size_t N = 500000 + 10;

int n, a[N], size[N], ans[N], ptr[N];
double k;

namespace Seg
{
    int v[N << 2];
    int t[N << 2];
    #define LV (p << 1)
    #define RV (LV | 1)
    #define L (v[LV])
    #define R (v[RV])
    #define P (v[p])
    void build(int p, int l, int r)
    {
        P = l;
        if (l == r) return;
        int mid = (l + r) >> 1;
        build(LV, l, mid);
        build(RV, mid + 1, r);
    }
    void update(int p)
    {
        P = std::min(L, R);
    }
    void pushdown(int p)
    {
        if (t[p])
        {
            L += t[p];
            R += t[p];
            t[LV] += t[p];
            t[RV] += t[p];
            t[p] = 0;
        }
    }

    int pl, pr, px;
    signed pv;

    void add(int p, int l, int r)
    {
        if (pl <= l && r <= pr)
        {
            P += pv;
            t[p] += pv;
            return;
        }
        pushdown(p);
        int mid = (l + r) >> 1;
        if (pl <= mid) add(LV, l, mid);
        if (mid < pr) add(RV, mid + 1, r);
        update(p);
    }

    int get(int p, int l, int r)
    {
        if (l == r) return P >= px ? l : l + 1;
        pushdown(p);
        if (px > R)
            return get(RV, ((l + r) >> 1) + 1, r);
        else
            return get(LV, l, (l + r) >> 1);
    }

    void add(int l, signed v)
    {
        pl = l, pr = n, pv = v;
        add(1, 1, n);
    }

    int get(int p)
    {
        px = p;
        return get(1, 1, n);
    }
}

#define FA(a) ((int)(((double)a) / k))

signed main(void)
{
    scanf("%d %lf", &n, &k);
    for (int i = 1; i <= n; ++i) a[i] = read;
    std::sort(a + 1, a + n + 1, std::greater<int>());
    Seg::build(1, 1, n);
    for (int i = n; i; --i)
    {
        size[i] += 1;
        size[FA(i)] += size[i];
        ptr[i] = a[i] == a[i + 1] ? ptr[i + 1] + 1 : 0;
    }
    for (int i = 1; i <= n; ++i)
    {
        static bool vis[N];
        static int fa;
        fa = FA(i);
        if (fa && !vis[fa])
        {
            Seg::add(ans[fa], size[fa] - 1);
            fprintf(stderr, "change(%d, %d)\n", ans[fa], size[fa] - 1);
            vis[fa] = true;
        }
        int tg = Seg::get(size[i]);
        tg += ptr[tg];
        ans[i] = tg;
        fprintf(stderr, "change(%d, %d)\n", tg, -size[i]);
        Seg::add(tg, -size[i]);
    }
    for (int i = 1; i <= n; ++i) printf("%d ", a[ans[i]]);
}
点赞

发表评论

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