yeyou26 的博客
浅谈 NOIP 数据结构
yeyou26 LV 6 @ 2025-7-2 17:26:51

简单 NOIP 数据结构

栈

栈的实现

std::stack常数较大，建议手写

int stk[N], top = 0; stk[++top] = x; // 入栈 x = stk[top]; // 查询 top--; // 弹栈 x = top; // 元素个数

单调栈

例题

由于是“后面第一个”，所以从后往前考虑对于一个数据，如果他比之前考虑过的一些数据（下标大）还大，显然之前的那些数据都不可能再成为答案，都 pop 掉即可。

队列

队列的实现

std::queue 常数较大，建议手写

int q[N], frt = 0, tail = 0; x = (tail - frt); // 元素个数 q[++tail] = x; // 入队 frt++; // 出队 x = q[frt + 1]; // 队首 x = q[tail]; // 队尾

单调队列

例题

相比于单调栈，多了弹出过期元素的功能。

$\color{red}{如果一个人比你来的晚，还比你强，那你永远也打不过他}$

堆

堆的实现

std::priority_queue pq;

真有人手写堆？

可删堆

struct heap
{
    std::priority_queue<int> q1, q2;
    void Push(int x) { q1.push(x); }
    void Pop(int x) { q2.push(x); }
    int Top()
    {
        while (q2.size() && q1.top() == q2.top()) q1.pop(), q2.pop();
        return q1.top();
    }
};

冰茶姬

路径压缩

顾名思义，查询时压缩路径，只维护集合信息，毁坏路径信息。

均摊最坏查询时间复杂度 $O(\log {n})$

int fa[N], n; int Find(int x) { return (fa[x] == x) ?: x : fa[x] = Find(fa[x]); } for (int i = 1; i <= n; i++) fa[i] = i;

按秩合并

也就是一定秩序合并，常见的有两种：按高度合并或启发式合并（即按大小合并），保留路径信息，常用于可持久化数据结构，联赛少见

不要忘了初始化!!!!!!!!!!!

查询时间复杂度 $O(\log n)$

void Union(int x, int y) //启发式合并
{
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (size[x] < size[y]) std::swap(x, y);
    size[x] += size[y];
    fa[y] = x;
}
void Union(int x, int y) //按高度合并
{
    x = Find(x), y = Find(y);
    if (x == y) return;
    if (rk[x] < rk[y]) std::swap(x, y);
    fa[y] = x;
    if (rk[x] == rk[y]) rk[x]++;
}

路径压缩+按秩合并

当同时使用路径压缩与按秩合并，单次查询复杂度将是均摊 $O(\alpha{(n)})$ 其中， $\alpha(n)$ 是阿克曼函数的反函数，增长极为缓慢参考:$\quad \alpha(3)=1 \quad \alpha(7)=2 \quad \alpha(61)=3 \quad \alpha(2^{65533})<4$

在联赛应用中，一般不会有把时间复杂度压到这么低的需求，用路径压缩就足已解决大部分问题。

ST表

通过 $O(n\log n)$ 预处理做到序列任意区间最值 $O(1)$ 查询，不支持删改

struct stb
{
    int a[N], n, f[M][N],lg[N];
    void Init()
    {
        for (int i = 1; i <= n; i++) f[0][i] = a[i];
        for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
        for (int k = 1; k <= lg[n] + 1; k++)
        {
            for (int i = 1; i + (1 << k) - 1 <= n; i++) f[k][i] = std::max(f[k - 1][i], f[k - 1][i + (1 << (k - 1))]);
        }
    }
    int Query(int l, int r) { return std::max(f[lg[r - l + 1]][l], f[lg[r - l + 1]][r + 1 - (1 << lg[r - l + 1])]); }
}st;

树状数组

朴素树状数组

实现

struct binary
{
    int n, a[N];
    int Query(int idx)
    {
        int res = 0;
        while (idx)
        {
            res += a[idx];
            idx -= idx & (-idx);
        }
        return res;
    }
    void Modify(int idx, int val)
    {
        while (idx <= n)
        {
            a[idx] += val;
            idx += idx & (-idx);
        }
    }
} bit;

应用

单次操作时间复杂度 $O(\log n)$

朴素 bit 可以解决单点修改区间查询

可以使用 bit 维护原序列的差分序列来实现区间修改单点查询

~~远小于线段树的空间复杂度，常数时间复杂度，码量和 debug 时间~~

lazy tag：权值bit 高维前缀和bit 二分bit 倍增bit

二维树状数组

namespace bit
{
    int a[M][N];
    void Modify(int x, int y, int val)
    {
        while (x <= M - 2)
        {
            int ty = y;
            while (ty <= N - 2) a[x][ty] = std::max(val, a[x][ty]), ty += -ty & ty;
            x += -x & x;
        }
    }
    int Query(int x, int y)
    {
        int res = 0;
        while (x)
        {
            int ty = y;
            while (ty) res = std::max(a[x][ty], res), ty -= -ty & ty;
            x -= -x & x;
        }
        return res;
    }
} // namespace bit

分块

简单分块：使用均值不等式求出最佳块长，使得块长与块数同阶。

线段树、进阶线段树与线段树常用技巧

线段树本质

可以用线段树维护的信息必须满足可加性且具备结合律。这是显然的，因为线段树的工作原理就是用两个孩子节点的信息合并为自己的信息。

技巧“标记永久化”会对此深入研究。

朴素线段树

#define ul (u << 1)
#define ur (u << 1 | 1)
#define cl tr[ul]
#define cr tr[ur]
#define cu tr[u]
struct segment
{
    原始信息
    struct node
    {
        int l, r;
        这棵树维护的信息
    } tr[N * 一般是4倍，也可能8倍];
    void Pushup(int u) { 用左右孩子的信息更新自己的信息; }
    void Build(int u, int l, int r)
    {
        cu.l = l, cu.r = r;
        初始化叶子节点
        if (l >= r) return;
        int mid = (l + r) / 2;
        Build(ul, l, mid);
        Build(ur, mid + 1, r);
        Pushup(u);
    }
    void Modify(int u, int l, int r, int val)
    {
        if (l <= cu.l && r >= cu.r) return 更新自己信息, void();
        int mid = (cu.l + cu.r) / 2;
        更新左右孩子
        Pushup(u);
    }
    int Query(int u, int l, int r)
    {
        if (l <= cu.l && r >= cu.r) return 自己的信息;
        int mid = (cu.l + cu.r) / 2;
        获取左右孩子信息
        return 信息;
    }
} sg;

技巧

lazy tag

对于易下放的信息（如加和），我们可以使用lazy tag实现区间修改。在查询到有 lazy tag 的节点时再下放即可，保证了时间复杂度。

维护区间和的线段树板子 :

struct segment
{
    int n, a[N];
    struct node
    {
        int l, r, sum, lazy;
    } tr[N * 8];
    void Pushup(int u) { cu.sum = cl.sum + cr.sum; }
    void Pushdown(int u)
    {
        if (cu.lazy)
        {
            cl.lazy += cu.lazy, cr.lazy += cu.lazy;
            cl.sum += cu.lazy * (cl.r - cl.l + 1);
            cr.sum += cu.lazy * (cr.r - cr.l + 1);
            cu.lazy = 0;
        }
    }
    void Build(int u, int l, int r)
    {
        cu.l = l, cu.r = r, cu.sum = a[l], cu.lazy = 0;
        if (l >= r) return;
        int mid = (l + r) / 2;
        Build(ul, l, mid);
        Build(ur, mid + 1, r);
        Pushup(u);
    }
    void Modify(int u, int l, int r, int val)
    {
        if (l <= cu.l && r >= cu.r) return cu.lazy+=val, cu.sum += val * (cu.r - cu.l + 1), void();
        Pushdown(u);
        int mid = (cu.l + cu.r) / 2;
        if (l <= mid) Modify(ul, l, r, val);
        if (r >= mid + 1) Modify(ur, l, r, val);
        Pushup(u);
    }
    int Query(int u, int l, int r)
    {
        if (l <= cu.l && r >= cu.r) return cu.sum;
        Pushdown(u);
        int mid = (cu.l + cu.r) / 2;
        int res = 0;
        if (l <= mid) res += Query(ul, l, r);
        if (r >= mid + 1) res += Query(ur, l, r);
        return res;
    }
} sg;

标记永久化

对于难以下放的信息，考虑标记永久化，每次查询返回途中累加标记。

什么样的信息可以使用标记永久化？

信息支持 pushup

信息支持快速计算节点上的标记对结果的贡献

信息标记具有交换律

一个特例是区间赋值。赋值操作显然不具有交换律，但可维护时间戳转化为求时间戳最值。

信息不支持 pushup

信息支持快速计算一个不包含当前区间的修改对当前区间的影响

信息支持快速计算节点上的标记对结果的贡献

信息标记具有交换律

模板代码

以加和分为例演示标记永久化

struct segment
{
    int n, a[N];
    struct node
    {
        int l, r, sum, lazy;
    } tr[N * 4];
    void Build(int u, int l, int r)
    {
        cu.l = l, cu.r = r, cu.sum = a[l], cu.lazy = 0;
        if (l >= r) return;
        int mid = (l + r) / 2;
        Build(ul, l, mid);
        Build(ur, mid + 1, r);
        cu.sum = cl.sum + cr.sum;
    }
    void Modify(int u, int l, int r, int val)
    {
        int len = (std::min(r, cu.r) - std::max(l, cu.l) + 1);
        cu.sum += val * len;
        if (len == cu.r - cu.l + 1) return cu.lazy += val, void();
        int mid = (cu.l + cu.r) / 2;
        if (l <= mid) Modify(ul, l, r, val);
        if (r >= mid + 1) Modify(ur, l, r, val);
    }
    int Query(int u, int l, int r)
    {
        int len(std::min(r, cu.r) - std::max(l, cu.l) + 1);
        if (len == cu.r - cu.l + 1) return cu.sum;
        int res = len * cu.lazy;
        int mid = (cu.l + cu.r) / 2;
        if (l <= mid) res += Query(ul, l, r);
        if (r >= mid + 1) res += Query(ur, l, r);
        return res;
    }
} sg;

动态开点

对于任意一个节点，只有在被使用前才创建。

通过记录左右儿子的编号来找孩子，而不是使用完全二叉树的编号法则。

分为完全动态开点和不完全动态开点。不完全动态开点保留建树过程，可以把线段树空间复杂度常数降为不使用动态开点的一半(即省去了朴素线段树中完全不可能用到的节点的内存)。完全动态开点可以做到更小的空间复杂度，通常用于解决值域极大的问题，同时由于子树可能不完整，完全动态开点必须搭配标记永久化使用。 代码 lazy tag

扫描线

一个朴素的求矩形面积并的扫描线板子

namespace scanning_line
{
    enum
    {
        N = 100005
    }; // 矩形个数
#define lc (u << 1)
#define rc (u << 1 | 1)
    int posx[N * 2], n, posx_cnt;
    struct line
    {
        int x1, x2, y, type;
        bool operator<(const line &o) const
        {
            return y < o.y;
        }
    } ln[N * 2];
    struct node
    {
        int l, r, cnt, len;
    } tr[N * 2 * 4]; // 矩形个数为N x坐标关键点数量最多为2N 所以线段树节点数最多8N
    void Build(int u, int l, int r)
    {
        tr[u] = {l, r, 0, 0};
        if (l >= r) return;
        int mid = (l + r) / 2;
        Build(lc, l, mid);
        Build(rc, mid + 1, r);
    }
    void Pushup(int u)
    {
        if (tr[u].cnt) tr[u].len = posx[tr[u].r + 1] - posx[tr[u].l];
        else if (tr[u].l == tr[u].r) tr[u].len = 0; // 防止叶子节点访问不存在的孩子导致越界 也可以给节点数*2解决
        else tr[u].len = tr[lc].len + tr[rc].len;
    }
    void Modify(int u, int l, int r, int val)
    {
        if (l <= tr[u].l && r >= tr[u].r)
        {
            tr[u].cnt += val;
            Pushup(u);
            return;
        }
        int mid = (tr[u].l + tr[u].r) / 2;
        if (l <= mid) Modify(lc, l, r, val);
        if (r >= mid + 1) Modify(rc, l, r, val);
        Pushup(u);
    }
    void Init()
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            int x1, x2, y1, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            ln[i] = {x1, x2, y1, 1};
            ln[i + n] = {x1, x2, y2, -1};
            posx[i] = x1, posx[i + n] = x2;
        }
        n *= 2;
        std::sort(posx + 1, posx + 1 + n);
        std::sort(ln + 1, ln + 1 + n);
        posx_cnt = std::unique(posx + 1, posx + 1 + n) - posx - 1;
        Build(1, 1, posx_cnt);
    }
    long long ans = 0;
    void Scan()
    {
        for (int i = 1; i <= n - 1; i++)
        {
            int l = std::lower_bound(posx + 1, posx + 1 + posx_cnt, ln[i].x1) - posx;
            int r = std::lower_bound(posx + 1, posx + 1 + posx_cnt, ln[i].x2) - posx;
            Modify(1, l, r - 1, ln[i].type);
            ans += 1ll * tr[1].len * (ln[i + 1].y - ln[i].y);
        }
    }
#undef lc
#undef rc

} // namespace scanning_line

权值线段树

什么是权值线段树

朴素线段树维护的是信息，按元素个数开空间，维护的是特定信息

权值线段树维护的是元素个数，按值域开空间，维护了一堆桶

朴素权值线段树

由于没有板子题，笔者乱胡了一个没有正确性保证的朴素线段树，谨防食物中毒

struct bucker_segment
{
    int n, b[M];
    struct node
    {
        int l, r, cnt;
    } tr[M * 4];
    inline void Pushup(int u) { cu.cnt = cl.cnt + cr.cnt; }
    void Build(int u, int l, int r)
    {
        cu.l = l, cu.r = r, cu.cnt = b[l];
        if (l >= r) return;
        int mid = (l + r) / 2;
        Build(ul, l, mid);
        Build(ur, mid + 1, r);
        Pushup(u);
    }
    void Modify(int u, int val, int cnt)
    {
        if (cu.l == cu.r) return cu.cnt += cnt, void();
        int mid = (cu.l + cu.r) / 2;
        if (val <= mid) Modify(ul, val, cnt);
        else Modify(ur, val, cnt);
        Pushup(u);
    }
    int Query(int u, int l, int r)
    {
        if (l <= cu.l && r >= cu.r) return cu.cnt;
        int mid = (cu.l + cu.r) / 2;
        int res = 0;
        if (l <= mid) res += Query(ul, l, r);
        if (r >= mid + 1) res += Query(ur, l, r);
        return res;
    }
    int Kth(int u, int k)
    {
        if (cu.l == cu.r) return cu.l;
        if (cl.cnt >= k) return Kth(ul, k);
        else return Kth(ur, k - cl.cnt);
    }
}sg;

珂朵莉树

Chtholly Tree

名字由来： CF896C

工作远离：把序列划分为若干个闭区间，每个区间上每个元素值相同，使用 set 维护整个序列，任何操作都是直接暴力修改。

效率：可以证明，在保证数据随机的前提下，Chtholly Tree(以下简称ctt)的时空表现均吊打线段树

应用：频繁区间赋值或数据随机的序列问题，在不知道怎么维护区间信息的时候可以用来骗分

要点/易错点：见代码

code

struct Chtholly
{
    struct node
    {
        int l, r;
        mutable int val;                                                        // set 不支持随机修改
        node(int _l, int _r = -1, int _val = 0) { l = _l, r = _r, val = _val; } // 默认值的原因见split第一行
        inline bool operator<(const node &o) const { return l < o.l; }
    };
    std::set<node> st;
    typedef std::set<node>::iterator itrt;
    Chtholly(int _n) { st.insert((node{1, _n + 1, 0})); } // 理解了ctt的工作方法就会明白这里要+1
    inline itrt Split(int idx)
    {
        auto it = st.lower_bound((node{idx}));
        if (it != st.end() && it->l == idx) return it;
        --it;
        int l = it->l, r = it->r, val = it->val; // insert 函数返回一个pair first是迭代器 second是bool表示是否插入成功
        return st.erase(it), st.insert((node){l, idx - 1, val}), st.insert((node){idx, r, val}).first;
    }
    inline itrt Assign(int l, int r, int val) // ctt的核心：区赋值
    {
        itrt itr = Split(r + 1), itl = Split(l); // 必须先split右端点 可以脑渲一下先split左端点的后果
        return st.erase(itl, itr), st.insert((node){l, r, val}).first;
    }
};

线段树分裂/合并

lazy tag

李超线段树

lazy tag

吉司机线段树

lazy tag

平衡树

![[Pasted image 20240805180456.png]]

(这题实际上正解是树状数组) 如你所见，虽然在考纲里，但是平衡树考频感人。如果时间紧的话完全可以不学，此处仅介绍两种最常用平衡树的最基本操作(包括区间反转)

FHQ treap

tags : 码量小难度小适用性高

朴素 FHQ

#define ul tr[u].l
#define ur tr[u].r
#define cu tr[u]
#define cl tr[ul]
#define cr tr[ur]
#define cx tr[x]
#define cy tr[y]
struct fhq_treap
{
    struct node
    {
        int l, r;
        long unsigned int key;
        int val, siz;
    } tr[N];
    int idx = 0, root;
    std::mt19937 rd;
    inline int Newnode(int val) { return tr[++idx] = {0, 0, rd.operator()(), val, 1}, idx; }
    inline void Pushup(int u) { cu.siz = 1 + cl.siz + cr.siz; }
    void Splitval(int u, int val, int &x, int &y)
    {
        if (!u) return x = y = 0, void();
        if (cu.val <= val) x = u, Splitval(ur, val, ur, y);
        else y = u, Splitval(ul, val, x, ul);
        return Pushup(u), void();
    }
    void Splitsiz(int u, int siz, int &x, int &y)
    {
        if (!u) return x = y = 0, void();
        if (cl.siz >= siz) y = u, Splitsiz(ul, siz, x, ul);
        else x = u, Splitsiz(ur, siz - cl.siz - 1, ur, y);
        return Pushup(u), void();
    }
    int Merge(int x, int y)
    {
        if (!x || !y) return x + y;
        if (cx.key < cy.key) return cx.r = Merge(cx.r, y), Pushup(x), x;
        else return cy.l = Merge(x, cy.l), Pushup(y), y;
    }
    void Insert(int val)
    {
        int x, y, z = Newnode(val);
        Splitval(root, val, x, y);
        root = Merge(Merge(x, z), y);
    }
    void Delete(int val)
    {
        int x, y, z;
        Splitval(root, val - 1, x, y);
        Splitval(y, val, y, z);
        root = Merge(Merge(x, Merge(cy.l, cy.r)), z);
    }
    int Rank(int val)
    {
        int x, y, res;
        Splitval(root, val - 1, x, y);
        res = cx.siz + 1;
        return root = Merge(x, y), res;
    }
    int Kth(int &rt, int k)
    {
        int x, y, z, res;
        Splitsiz(rt, k - 1, x, z);
        Splitsiz(z, 1, y, z);
        return res = cy.val, rt = Merge(Merge(x, y), z), res;
    }
    int Pre(int val)
    {
        int x, y, res;
        Splitval(root, val - 1, x, y);
        return res = Kth(x, cx.siz), root = Merge(x, y), res;
    }
    int Suf(int val)
    {
        int x, y, res;
        Splitval(root, val, x, y);
        return res = Kth(y, 1), root = Merge(x, y), res;
    }
} tp;

文艺 FHQ(区间 reverse)

在文艺平衡树中，我们不使用 BST 的性质来维护元素有序，而是利用其中序遍历就是原序列的特点，用来维护一段连续的序列，而聪明的你已经发现 fhq 分裂操作刚好可以拆出一段连续的区间，而区间反转行为更是只需要递归交换左右孩子即可实现，于是我们有了这个板子。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::ios;

const int N = 100004;

#define ul tr[u].l
#define ur tr[u].r
#define cu tr[u]
#define cx tr[x]
#define cy tr[y]
#define cl tr[ul]
#define cr tr[ur]
struct fhq_treap
{
    struct node
    {
        int l, r;
        long unsigned key;
        int val, siz, tag;
    } tr[N];
    int idx = 0, root = 0;
    std::mt19937 rd;
    inline int Newnode(int val) { return tr[++idx] = {0, 0, rd.operator()(), val, 1, 0}, idx; }
    inline void Pushup(int u) { cu.siz = cl.siz + cr.siz + 1; }
    inline void Pushdown(int u)
    {
        if (cu.tag) std::swap(ul, ur), cl.tag ^= 1, cr.tag ^= 1, cu.tag = 0;
    }
    void Splitsiz(int u, int siz, int &x, int &y)
    {
        if (!u) return x = y = 0, void();
        Pushdown(u);
        if (cl.siz >= siz) y = u, Splitsiz(ul, siz, x, ul);
        else x = u, Splitsiz(ur, siz - cl.siz - 1, ur, y);
        return Pushup(u), void();
    }
    int Merge(int x, int y)
    {
        if (!x || !y) return x + y;
        if (cx.key < cy.key) return Pushdown(x), cx.r = Merge(cx.r, y), Pushup(x), x;
        else return Pushdown(y), cy.l = Merge(x, cy.l), Pushup(y), y;
    }
    void Middle(int u)
    {
        if (!u) return;
        if (cu.tag) cl.tag ^= 1, cr.tag ^= 1, std ::swap(ul, ur), cu.tag = 0;
        Middle(ul), cout << cu.val << ' ', Middle(ur);
    }
    void Insert(int val) { root = Merge(root, Newnode(val)); }
} tp;

namespace mf
{
    int n, m;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    using namespace mf;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) tp.Insert(i);
    for (int i = 1; i <= m; i++)
    {
        int l, r, x, y, z;
        cin >> l >> r;
        tp.Splitsiz(tp.root, r, y, z);
        tp.Splitsiz(y, l - 1, x, y);
        tp.cy.tag ^= 1;
        tp.root = tp.Merge(tp.Merge(x, y), z);
    }
    tp.Middle(tp.root);
    return 0;
}

Splay

tags : 你的 fhq 在一些问题上表现得比较松弛，而你的 splay 恰好弥补了这一点

(人话：splay 码量大还不比 fhq 快，还是 fhq 用的多，偶尔迫不得已用下 splay，基本用不到第三种平衡树)

代码：笔者已经调这个傻∎东西调了半年了（确信）~~到现在也没调出来，于是摆了~~ ![[Pasted image 20240805202138.png]]

Summary & Reconstruct from

基于线段树和树状数组的序列维护 - james1 的博客 (james1badcreeper.github.io) 数据结构的常用维护方法 - james1 的博客 (james1badcreeper.github.io) NOI 一轮复习 II：数据结构 A - james1 的博客 (james1badcreeper.github.io) OI 模板合集 - 樱雪喵 - 博客园 (cnblogs.com) 线段树进阶 Part 1 - 洛谷专栏 (luogu.com.cn) 标记永久化 - wozaixuexi - 博客园 (cnblogs.com) 【算法学习】Fhq-Treap（无旋Treap） - 粉兔 - 博客园 (cnblogs.com) bilibili.com/video/BV1kY4y1j7LC/ bilibili.com/video/BV1pd4y1D7Nu/ 二叉搜索树与平衡树 - james1 的博客 (james1badcreeper.github.io) C06【模板】FHQ Treap P3391 文艺平衡树_哔哩哔哩_bilibili 详解权值线段树 - Seaway-Fu - 博客园 (cnblogs.com) 浅谈珂朵莉树（Chtholly Tree）——暴力而玄学的数据结构-CSDN博客珂朵莉树_willem, chtholly and seniorious-CSDN博客珂朵莉·诺塔·瑟尼欧里斯 - 萌娘百科万物皆可萌的百科全书 (moegirl.org.cn)

浅谈 NOIP 数据结构

简单 NOIP 数据结构

栈

栈的实现

单调栈

队列

队列的实现

单调队列

堆

堆的实现

可删堆

冰茶姬

路径压缩

按秩合并

路径压缩+按秩合并

ST表

树状数组

朴素树状数组

实现

应用

二维树状数组

分块

线段树、进阶线段树与线段树常用技巧

线段树本质

朴素线段树

技巧

lazy tag

标记永久化

什么样的信息可以使用标记永久化？

信息支持 pushup

信息不支持 pushup

模板代码

动态开点

扫描线

权值线段树

什么是权值线段树

朴素权值线段树

珂朵莉树

Chtholly Tree

code

线段树分裂/合并

李超线段树

吉司机线段树

平衡树

FHQ treap

朴素 FHQ

文艺 FHQ(区间 reverse)

Splay

Summary & Reconstruct from

状态

开发

支持

还没有账户？

登录