洛谷 P2596 题解

admin 2021-05-02 AM 126℃ 0条

题目链接

前言

这是为数不多的 FHQ-Treap 题解。

唯一使用这种思路的题解是 Kubic 的题解(博文已隐藏,目前在题解区第三页),但是我觉得这片题解对于我这种 FHQ-Treap 萌新非常不友好,所以决定自己写一篇。

分析

首先,将节点与书的编号对应,编号为 $i$ 的书的信息就放在平衡树的第 $i$ 个节点里,其权值初始为它的排名,无论任何时候,这本书的位置在树上对应的权值在所有权值中从小到大的排名就是这本书从上到下的位置。维护所有权值中最小的权值 $Min$ 和最大的权值 $Max$。

考虑如何维护这些操作。

  • $Top(s)$ 操作

$Min \gets Min-1$,将树上第 $s$ 个节点的权值改为 $Min$。具体地,依次执行:

split(root, val[s], x, z);
split(x, val[s] - 1, x, y);
val[s] = --Min;
root = merge(merge(y, x), z);
  • $Bottom(s)$ 操作

$Max \gets Max+1$,将树上第 $s$ 个节点的权值改为 $Max$。具体地,依次执行:

split(root, val[s], x, z);
split(x, val[s] - 1, x, y);
val[s] = ++Max;
root = merge(merge(x, z), y);
  • $Insert(s, t)$ 操作

    1. 如果 $t=0$,不管。
    2. 如果 $t=1$,设 $p$ 为 $s$ 的后继的编号。把 $s$ 和 $p$ 分裂出来,然后交换 $s$ 和 $p$ 的所有信息,最后合并。具体地,依次执行:
    p = nxt(s);
    split(root, val[s] - 1, root, x);
    split(x, val[s], x, y);
    split(y, val[p], y, z);
    swp(x, y); // 交换 x 和 y 的所有信息
    root = merge(merge(root, y), merge(x, z));
    1. 如果 $t=-1$,类似 $t=1$ 处理。
  • $Ask(s)$ 操作

返回 $rk(val_s) - 1$,其中 $rk$ 返回排名。

  • $Query(s)$ 操作

返回 $kth(s)$,其中 $kth$ 返回第 $k$ 大。

解决

#include <algorithm>
#include <cstdio>
#include <iostream>

const int N = 8e4 + 5;

namespace FHQ_Treap
{
    int val[N], lc[N], rc[N], siz[N], rnd[N];
    int root, x, y, z;

    void swp(int x, int y)
    {
        std::swap(val[x], val[y]);
        std::swap(lc[x], lc[y]);
        std::swap(rc[x], rc[y]);
        std::swap(siz[x], siz[y]);
        std::swap(rnd[x], rnd[y]);
    }

    void split(int p, int k, int &a, int &b)
    {
        if (p == 0)
        {
            a = b = 0;
            return;
        }
        else if (val[p] <= k)
            a = p, split(rc[p], k, rc[p], b);
        else
            b = p, split(lc[p], k, a, lc[p]);
        siz[p] = siz[lc[p]] + siz[rc[p]] + 1;
    }

    int merge(int a, int b)
    {
        if (a == 0 || b == 0)
            return a + b;
        else if (rnd[a] < rnd[b])
        {
            rc[a] = merge(rc[a], b), siz[a] = siz[lc[a]] + siz[rc[a]] + 1;
            return a;
        }
        else
        {
            lc[b] = merge(a, lc[b]), siz[b] = siz[lc[b]] + siz[rc[b]] + 1;
            return b;
        }
    }

    int New(int id, int v)
    {
        val[id] = v, siz[id] = 1, rnd[id] = std::rand();
        return id;
    }

    void insert(int id, int order)
    {
        root = merge(root, New(id, order));
    } // order 单调递增,不需要 split

    int pre(int k)
    {
        split(root, val[k] - 1, x, y);
        int p = x;
        while (rc[p])
            p = rc[p];
        root = merge(x, y);
        return p;
    }

    int nxt(int k)
    {
        split(root, val[k], x, y);
        int p = y;
        while (lc[p])
            p = lc[p];
        root = merge(x, y);
        return p;
    }

    int kth(int k)
    {
        int p = root;
        while (1)
        {
            if (siz[lc[p]] >= k)
                p = lc[p];
            else if (siz[lc[p]] + 1 == k)
                return p;
            else
                k -= siz[lc[p]] + 1, p = rc[p];
        }
    }

    int rank(int v)
    {
        split(root, v - 1, x, y);
        int res = siz[x] + 1;
        root = merge(x, y);
        return res;
    }
} // namespace FHQ_Treap

using namespace FHQ_Treap;

int n, m, Min, Max;
char op[10];

void Top(int s)
{
    split(root, val[s], x, z);
    split(x, val[s] - 1, x, y);
    val[s] = --Min;
    root = merge(merge(y, x), z);
}

void Bottom(int s)
{
    split(root, val[s], x, z);
    split(x, val[s] - 1, x, y);
    val[s] = ++Max;
    root = merge(merge(x, z), y);
}

void Insert(int s, int t)
{
    if (!t)
        return;
    else if (t == 1)
    {
        int p = nxt(s);
        split(root, val[s] - 1, root, x);
        split(x, val[s], x, y);
        split(y, val[p], y, z);
        swp(x, y); // 交换 x 和 y 的所有信息
        root = merge(merge(root, y), merge(x, z));
    }
    else
    {
        int p = pre(s);
        split(root, val[p] - 1, root, x);
        split(x, val[p], x, y);
        split(y, val[s], y, z);
        swp(x, y);
        root = merge(merge(root, y), merge(x, z));
    }
}

int Ask(int s)
{
    return rank(val[s]) - 1;
}

int Query(int s)
{
    return kth(s);
}

int main()
{
    scanf("%d%d", &n, &m);
    Min = 1, Max = n;
    for (int i = 1; i <= n; i++)
    {
        int p;
        scanf("%d", &p);
        insert(p, i);
    }
    while (m--)
    {
        int s, t;
        scanf("%s%d", op, &s);
        if (op[0] == 'T')
            Top(s);
        else if (op[0] == 'B')
            Bottom(s);
        else if (op[0] == 'I')
            scanf("%d", &t), Insert(s, t);
        else if (op[0] == 'A')
            printf("%d\n", Ask(s));
        else
            printf("%d\n", Query(s));
    }
    return 0;
}
标签: 数据结构, FHQ-Treap

非特殊说明,本博所有文章均为博主原创。

上一篇 没有了
下一篇 洛谷 P3660 题解

评论啦~