【题解】普通平衡树 Leafy Tree BZOJ – 3224

于由Remmina发布

Remmina 酱白天要做文化课，只能晚上来写题了，现在凌晨啦

刚开始学平衡树好吃力啊

蟹蟹 XZY 学长之前的指导，总算是照着论文把 Leafy Tree 写出来啦

到时候可能会发文章（或者 PPT）来讲讲这个算法，确实还算比较好写的吧

当做模板放在这里啦，具体操作论文讲的很清楚，就是 CTSC 的论文集的那个

主要是实现细节论文没讲，细节可以看代码啦哈哈哈哈哈哈

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

const double alp = 1 - sqrt(2) * 0.5, bta = (1 - 2 * alp) / (1 - alp);

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct N {int s[2], d, sz;} e[NS << 1];

int n, root, sz;

stack<int> rub;

int New(int d)
{
    int a;
    if (rub.empty()) a = ++sz;
    else {a = rub.top(); rub.pop();}
    e[a].d = d, e[a].sz = 1, e[a].s[0] = e[a].s[1] = 0;
    return a;
}

void Del(int a) {rub.push(a);}

void pup(int a)
{
    if (!e[a].s[0]) return;
    e[a].sz = e[e[a].s[0]].sz + e[e[a].s[1]].sz;
    e[a].d = e[e[a].s[1]].d;
}

void rot(int a, int x)
{
    if (!e[a].s[0]) return;
    int b = e[a].s[x ^ 1];
    e[a].s[x ^ 1] = e[a].s[x], e[a].s[x] = e[e[a].s[x ^ 1]].s[x];
    e[e[a].s[x ^ 1]].s[x] = e[e[a].s[x ^ 1]].s[x ^ 1];
    e[e[a].s[x ^ 1]].s[x ^ 1] = b, pup(e[a].s[x ^ 1]), pup(a);
}

void mt(int a)
{
    if (!e[a].s[0]) return;
    int x;
    if (e[e[a].s[0]].sz < e[a].sz * alp) x = 1;
    else if (e[e[a].s[1]].sz < e[a].sz * alp) x = 0;
    else return;
    if (e[e[e[a].s[x]].s[x ^ 1]].sz >= e[e[a].s[x]].sz * bta)
        rot(e[a].s[x], x ^ 1);
    rot(a, x);
}

void Insert(int d, int& a)
{
    if (!a) {a = New(d); return;}
    if (!e[a].s[0])
    {
        e[a].s[0] = New(d), e[a].s[1] = New(e[a].d);
        if (d > e[a].d) swap(e[a].s[0], e[a].s[1]);
    }
    else Insert(d, e[a].s[d > e[e[a].s[0]].d]);
    pup(a), mt(a);
}

void Erase(int d, int& a)
{
    if (!e[a].s[0]) {Del(a), a = 0; return;}
    int x = (d > e[e[a].s[0]].d);
    if (!e[e[a].s[x]].s[0])
    {
        if (e[e[a].s[x]].d != d) puts("Error!"), exit(0);
        Del(e[a].s[x]), Del(e[a].s[x ^ 1]), e[a] = e[e[a].s[x ^ 1]];
    }
    else Erase(d, e[a].s[x]);
    pup(a), mt(a);
}

int Order(int d, int a)
{
    if (!e[a].s[0]) return 0;
    if (e[e[a].s[0]].d < d) return Order(d, e[a].s[1]) + e[e[a].s[0]].sz;
    return Order(d, e[a].s[0]);
}

int Kth(int k, int a)
{
    if (!e[a].s[0]) return e[a].d;
    if (e[e[a].s[0]].sz <= k) return Kth(k - e[e[a].s[0]].sz, e[a].s[1]);
    return Kth(k, e[a].s[0]);
}

int Pre(int d, int a)
{
    if (!e[a].s[0])
    {
        if (e[a].d < d) return e[a].d;
        return INT_MIN;
    }
    if (e[e[a].s[0]].d < d) return max(e[e[a].s[0]].d, Pre(d, e[a].s[1]));
    return Pre(d, e[a].s[0]);
}

int Nxt(int d, int a)
{
    if (!e[a].s[0])
    {
        if (e[a].d > d) return e[a].d;
        return INT_MAX;
    }
    if (e[e[a].s[0]].d > d) return Nxt(d, e[a].s[0]);
    return Nxt(d, e[a].s[1]);
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1, o, x; i <= n; i += 1)
    {
        IN(o), IN(x);
        if (o == 1) Insert(x, root);
        else if (o == 2) Erase(x, root);
        else if (o == 3) printf("%d\n", Order(x, root) + 1);
        else if (o == 4) printf("%d\n", Kth(x - 1, root));
        else if (o == 5) printf("%d\n", Pre(x, root));
        else printf("%d\n", Nxt(x, root));
    }
    return 0;
}

参考了一下网上的代码重写了一份 maintain 和 rotate 的代码：

#include <bits/stdc++.h>

#define NS (100005)

using namespace std;

const int alp = 4;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct N {int s[2], d, sz;} e[NS << 1];

int n, root, sz;

stack<int> rub;

int New(int d)
{
    int a;
    if (rub.empty()) a = ++sz;
    else {a = rub.top(); rub.pop();}
    e[a].d = d, e[a].sz = 1, e[a].s[0] = e[a].s[1] = 0;
    return a;
}

void Del(int a) {rub.push(a);}

void pup(int a)
{
    if (!e[a].s[0]) return;
    e[a].sz = e[e[a].s[0]].sz + e[e[a].s[1]].sz;
    e[a].d = e[e[a].s[1]].d;
}

int Mix(int a, int b)
{
    int res = New(e[b].d);
    e[res].s[0] = a, e[res].s[1] = b, pup(res);
    return res;
}

void lrot(int a)
{
    if (!e[a].s[0]) return;
    int tmp = e[e[a].s[0]].s[0];
    Del(e[a].s[0]), e[a].s[1] = Mix(e[e[a].s[0]].s[1], e[a].s[1]);
    e[a].s[0] = tmp;
}

void rrot(int a)
{
    if (!e[a].s[0]) return;
    int tmp = e[e[a].s[1]].s[1];
    Del(e[a].s[1]), e[a].s[0] = Mix(e[a].s[0], e[e[a].s[1]].s[0]);
    e[a].s[1] = tmp;
}

void mt(int a)
{
    if (!e[a].s[0]) return;
    if (e[e[a].s[0]].sz > e[e[a].s[1]].sz * alp) lrot(a);
    else if (e[e[a].s[1]].sz > e[e[a].s[0]].sz * alp) rrot(a);
    if (e[e[a].s[0]].sz > e[e[a].s[1]].sz * alp)
        rrot(e[a].s[0]), lrot(a);
    else if (e[e[a].s[1]].sz > e[e[a].s[0]].sz * alp)
        lrot(e[a].s[1]), rrot(a);
}

void Insert(int d, int& a)
{
    if (!a) {a = New(d); return;}
    if (!e[a].s[0])
    {
        e[a].s[0] = New(d), e[a].s[1] = New(e[a].d);
        if (d > e[a].d) swap(e[a].s[0], e[a].s[1]);
    }
    else Insert(d, e[a].s[d > e[e[a].s[0]].d]);
    pup(a), mt(a);
}

void Erase(int d, int& a)
{
    if (!e[a].s[0]) {Del(a), a = 0; return;}
    int x = (d > e[e[a].s[0]].d);
    if (!e[e[a].s[x]].s[0])
    {
        if (e[e[a].s[x]].d != d) puts("Error!"), exit(0);
        Del(e[a].s[x]), Del(e[a].s[x ^ 1]), e[a] = e[e[a].s[x ^ 1]];
    }
    else Erase(d, e[a].s[x]);
    pup(a), mt(a);
}

int Order(int d, int a)
{
    if (!e[a].s[0]) return 0;
    if (e[e[a].s[0]].d < d) return Order(d, e[a].s[1]) + e[e[a].s[0]].sz;
    return Order(d, e[a].s[0]);
}

int Kth(int k, int a)
{
    if (!e[a].s[0]) return e[a].d;
    if (e[e[a].s[0]].sz <= k) return Kth(k - e[e[a].s[0]].sz, e[a].s[1]);
    return Kth(k, e[a].s[0]);
}

int Pre(int d, int a)
{
    if (!e[a].s[0])
    {
        if (e[a].d < d) return e[a].d;
        return INT_MIN;
    }
    if (e[e[a].s[0]].d < d) return max(e[e[a].s[0]].d, Pre(d, e[a].s[1]));
    return Pre(d, e[a].s[0]);
}

int Nxt(int d, int a)
{
    if (!e[a].s[0])
    {
        if (e[a].d > d) return e[a].d;
        return INT_MAX;
    }
    if (e[e[a].s[0]].d > d) return Nxt(d, e[a].s[0]);
    return Nxt(d, e[a].s[1]);
}

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1, o, x; i <= n; i += 1)
    {
        IN(o), IN(x);
        if (o == 1) Insert(x, root);
        else if (o == 2) Erase(x, root);
        else if (o == 3) printf("%d\n", Order(x, root) + 1);
        else if (o == 4) printf("%d\n", Kth(x - 1, root));
        else if (o == 5) printf("%d\n", Pre(x, root));
        else printf("%d\n", Nxt(x, root));
    }
    return 0;
}
分类： 文章

Remmina

No puzzle that couldn't be solved.

3 条评论

Qiuly · 2019年1月7日 6:06 下午

还是膜一波初三大佬%%%

回复

Qiuly · 2019年1月7日 6:05 下午

话说这道题可以用 vector 秒切诶…… 只有 20 行不到…… 比 Splay 快一些 (或许是我常数大)，内存使用小得多。网上也有大佬写过相关博客。

回复

    Remmina · 2019年1月7日 8:28 下午

    能用 vector？那真是太妙了
    我不会呀我还是太菜了

    回复

发表回复

Avatar placeholder

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