← 返回

平衡树学习记录

平衡树学习记录

二叉搜索树

定义

二叉搜索树是一种二叉树形数据结构，定义为：

基本操作

根据定义可以发现，二叉搜索树可以维护一些操作。

查找最大/最小值

显然根据定义，最小值为搜索树的最左子链的顶点；最大值为搜索树的最右子链的顶点。

搜索元素

如果我们要查找一个元素，可以从根节点出发，

如果当前节点大于所查找的节点，那么向左子树去查找；

如果当前节点小于所查找的节点，那么向右子树去查找。

直到根节点就为所查找的元素。

插入元素

如果我们要插入一个元素，显然和搜索的逻辑一致，可以从根节点出发，

如果当前节点大于插入元素，那么插入左子树；

如果当前节点小于插入元素，那么插入右子树。

如果当前节点等于插入元素，该节点的值次数增加 $1$ 。

如果当前节点为空，则插入此节点。

求元素排名

显然根据二叉搜索树的性质可得，我们可以首先从根节点一路跳到目标节点。

过程中，如果向右跳，则最终的答案要加上当前节点的左子树大小+当前节点重复次数。

最后的答案加上目标节点左子树的大小 $+1$ 即可。

查找排名为 k 的元素

同理按照求元素排名的方法递归即可。

性质

时间复杂度

显然，二叉搜索树的基本操作的时间复杂度只与树的高度成正比，即为复杂度 $O(h)$。

而对于一个 $n$ 个节点的二叉搜索树，其最优复杂度可以达到 $O(\log n)$，但最坏复杂度会退化为 $O(n)$。

平衡树

由于二叉搜索树虽然随机构造的期望高度可以达到 $\log n$，但实际中，搜索树有可能退化成链表。所以我们可以引出平衡树的概念，通过一定的操作维持输得高度（即平衡性），以达到降低时间复杂度的目的。

平衡性：一般情况下指一颗搜索树每一个节点的左右子树的高度差最多为 $1$。

Treap

Treap 是一种 弱平衡 的二叉搜索树。

Treap 维护时，每个节点除了维护的 权值（$val$） 之外，还额外维护一个随机的 优先级（$priority$）。之后构造出二叉搜索树，使得 $val$ 符合二叉搜索树的性质。同时构造一个 堆，使得 $priority$ 符合堆的性质。

通过这种方式就可以构造出一个 Treap。

例1

可以证明，通过这种方式构造的二叉搜索树的期望高度为 $\log n$。（这里笔者就不证明了，可以参考[OI-wiki#树高的证明](Treap - OI Wiki)）

FHQ-Treap（无旋Treap）

FHQ-Treap 是一种通过分裂合并来维护的 Treap，其优点是代码短，利于理解，所以如今被广泛的使用。当然，它存在常数过大的缺点。

这种维护方法的本质是因为 Treap 具有结构确定的性质。

首先，由于从一个根节点可以遍历出整个 Treap，所以我们可以将一棵 Treap 看作是一个区间。转化之后，就相当于得出了一个类似线段树的结构。

那么我们可以类比线段树的操作，比如一个区间 $[l,r]$ ，如果想要将其拆分为 $[l,v]$ 和 $[v+1,r]$，那么就相当于将这棵 Treap 按照 $x$ 分裂为两个小 Treap。

分裂

那么具体如何进行分裂操作呢？我们规定查找的值为 $v$，当前节点用 p 表示。

首先，我们创建两个空 Treap $t1,t2$。

最初，我们位于根节点 p ，如果给定的 $v$ 不小于 p 的权值，那么根据二叉搜索树的性质，将 p 和它的整个左子树全部划分到 $t1$。但是 p 的右子树中可能存在大于 $v$ 的节点，所以我们可以递归去继续分裂 p 的右子树，其中小于等于 $v$ 的节点同样划分到 $t1$，作为 p 的新的右子树。其他部分则划分到 $t2$。

同理若 $v$ 大于 p 的权值，使用类似的方法分裂即可。

合并

关于合并操作，对于两棵 Treap $t1,t2$，首先要满足 $t1$ 中的所有元素都小于等于 $t2$ 中的元素。（由于我们合并的树一般都是分裂出来的，所以不必单独考虑）

由于两棵 Treap 已经是有序的，我们只需要考虑两棵 Treap 哪个放在上面，即考虑应该将 $t1$ 作为 $t2$ 的左子树还是将 $t2$ 作为 $t1$ 的右子树。那么显然我们只需要根据 $priority$ 来分讨即可。这样操作就可以保证合并之后的树仍然符合 Treap 的性质。

代码解析

这样，我们就实现了 FHQ-Treap 的核心功能，其的所有操作都建立在分裂合并之上。那么代码就非常好写了。

结构定义

静态开一个结构体用来代表 Treap。

struct Point
{
    int l, r;
    int val, rnd;
    int size, sum;
} t[MaxN];
int tot = 0, root = 0;

l 和 r 分别代表左右儿子的节点下标。

val 和 rnd 分别代表节点的权值和优先值（随机）。

size 代表当前的子树大小。

sum 代表当前的子树和。

tot 用于确定每个点的下标，root 代表根节点的下标。

宏定义

为了方便书写，用 ls 代替 t[p].l，用 rs 代替 t[p].r。即分别代表左右子树。

pushup 函数
void pushup(int p)
{
    t[p].size = t[ls].size + t[rs].size + 1;
    t[p].sum = t[ls].sum + t[rs].sum + t[p].val;
}

类似线段树的 pushup ，用于在递归之后综合左右子树的信息并上传至节点 p 。

按值分裂（split_v）
void split_v(int p, int v, int &l, int &r)
{
    if (!p)
    {
        l = r = 0;
        return;
    }
    if (t[p].val <= v)
    {
        l = p;
        split_v(rs, v, rs, r);
    }
    else 
    {
        r = p;
        split_v(ls, v, l, ls);
    }
    pushup(p);
}

函数 split_v(p,v,&l,&r) 的含义为：

按排名分裂（split）
void split(int p, int v, int &l, int &r)
{
    if (!p)
    {
        l = r = 0;
        return;
    }
    if (t[ls].size + 1 <= v)
    {
        l = p;
        split(rs, v - (t[ls].size + 1), rs, r);
    }
    else
    {
        r = p;
        split(ls, v, l, ls);
    }
    pushup(p);
}

函数 split(p,v,&l,&r) 的含义为：

合并（merge）
int merge(int x, int y)
{
    if (!x || !y)
        return x + y;
    if (t[x].rnd < t[y].rnd)
    {
        t[x].r = merge(t[x].r, y);
        pushup(x);
        return x;
    }
    else        
    {
        t[y].l = merge(x, t[y].l);
        pushup(y);
        return y;
    }
}

函数 merge(x,y) 的含义为：

将以 x 为根的 Treap 和以 y 为根的 Treap 合并为一个Treap。

那么根据定义，只需要按照 rnd 来分讨即可。

创建新节点（newnode）
int newnode(int v)
{
    int p = ++tot;
    t[p].val = t[p].sum = v;
    t[p].l = t[p].r = 0;
    t[p].rnd = rand() * rand();
    t[p].size = 1;
    return p;
}

这个没什么好说的，对节点的每个元素赋初值即可。

建树（build）
int build(int l, int r)
{
    if (l == r)
        return newnode(a[l]);
    int mid = (l + r) >> 1;
    return merge(build(l, mid), build(mid + 1, r));
}

build 函数类似线段树的 build，分治递归建树，每个节点先单独创建，然后合并上传即可。

查询（query）
int query(int l, int r)
{
    int t1 = 0, t2 = 0, t3 = 0;
    split(root, l - 1, t1, t2);
    split(t2, r - l + 1, t2, t3);
    int ans = t[t2].sum;
    root = merge(t1, merge(t2, t3));
    return ans;
}

如果要查询 $[l,r]$ 区间之和，那么只需要先将 Treap 按照排名 $l-1$ 分裂为 $t1,t2$，然后将 $t2$ 再次按照 $r-l+1$ （即区间的长度）分裂为 $t2,t3$，那么只需要统计 $t2$ 的数据就是最终的区间和。

修改（change）
void change(int k, int v)
{
    int t1 = 0, t2 = 0, t3 = 0;
    split(root, k - 1, t1, t2);
    split(t2, 1, t2, t3);
	t[t2].val = v;
    t[t2].sum = t[t2].size * v;
    root = merge(t1, merge(t2, t3));
}

同理，如果要修改第 $k$ 位的值，那么将 Treap 按照 $k-1$ 排名分裂一次，再按照 $1$ 排名分裂一次。之后修改 $t2$ 的值并合并即可。

插入元素（addx）
void addx(int v)
{
    int t1 = 0, t2 = 0, t3 = 0;
    split_v(root, v, t1, t3);
    t2 = newnode(v);
    root = merge(t1, merge(t2, t3));
}

addx(v) 的含义为：

在 Treap 中插入一个新元素 $v$。

所以我们只需要按照 $v$ 值分裂为 $t1,t3$，并开一个新 Treap $t2$ 并将 $v$ 作为其值。然后依次合并 $t1,t2,t3$ 即可。

删除元素（delet）
void delet(int v)
{
    int t1 = 0, t2 = 0, t3 = 0;
    split_v(root, v - 1, t1, t2);
    split_v(t2, v, t2, t3);
    t2 = merge(t[t2].l, t[t2].r);
    root = merge(merge(t1, t2), t3);
}

delet(v) 的含义为：

在 Treap 中找到 $v$ 并将其删除。

所以我们可以按照 $v-1$ 值分裂为 $t1,t2$，然后按照 $v$ 值分裂为 $t2,t3$。

那么我们只需要将 $v$ 删除（即将 $t2$ 的左右子树合并），然后依次合并 $t1,t2,t3$ 即可。

求 v 的排名（rank）
int rank(int v)
{
    int t1 = 0, t2 = 0, t3 = 0;
    split_v(root, v - 1, t1, t3);
    int ans = t[t1].size + 1;
    root = merge(t1, t3);
    return ans;
}

如果要求 $v$ 的排名，那么只需要按照 $v-1$ 值分裂为 $t1,t2$，那么 $v$ 的排名就为 $t1$ 的大小 $+1$。

查询最大最小值（query_min,query_max）
int query_min(int p)
{
    while (ls)
    {
        p = ls;
    }
    return t[p].val;
}
int query_max(int p)
{
    while (rs)
    {
        p = rs;
    }
    return t[p].val;
}

由于 Treap 具有二叉搜索树的性质，那么显然以 $p$ 为根节点的 Treap的最左节点的值就为最小值，最右节点的值就为最大值。

如果要求解区间的最大最小值，可以先将其按排名分裂，然后对其中某个 Treap 求解即可。

求排名为 k 的值（ith）
int ith(int k)
{
    int t1 = 0, t2 = 0, t3 = 0;
    split(root, k, t1, t3);
    int ans = query_max(t1);
    root = merge(t1, t3);
    return ans;
}

显然只需要按照 $k$ 排名分裂为 $t1,t2$。那么答案就是 $t1$ 的最大值。

前驱后继（get_pre,get_nxt）
int get_pre(int v)
{        
    int t1 = 0, t2 = 0, t3 = 0;
    split_v(root, v - 1, t1, t3);
    int ans = query_max(t1);
    root = merge(t1, t3);
    return ans;
}
int get_nxt(int v)
{
    int t1 = 0, t2 = 0, t3 = 0;
    split_v(root, v, t1, t3);
    int ans = query_min(t3);
    root = merge(t1, t3);
    return ans;
}

如上，同理按照值分裂然后求取最大最小值即可。

完整代码

struct FHQ_treap
{
#define ls t[p].l
#define rs t[p].r
    struct Point
    {
        int l, r;
        int val, rnd;
        int size, sum;
    } t[MaxN];
    int tot = 0, root = 0;
    void pushup(int p)
    {
        t[p].size = t[ls].size + t[rs].size + 1;
        t[p].sum = t[ls].sum + t[rs].sum + t[p].val;
    }
    Point pushup(Point now, Point l, Point r)
    {
        now.size = l.size + r.size + 1;
        return now;
    }
    int newnode(int v)
    {
        int p = ++tot;
        t[p].val = t[p].sum = v;
        t[p].l = t[p].r = 0;
        t[p].rnd = rand() * rand();
        t[p].size = 1;
        return p;
    }
    void split_v(int p, int v, int &l, int &r)
    {
        if (!p)
        {
            l = r = 0;
            return;
        }
        if (t[p].val <= v)
        {
            l = p;
            split_v(rs, v, rs, r);
        }
        else
        {
            r = p;
            split_v(ls, v, l, ls);
        }
        pushup(p);
    }
    void split(int p, int v, int &l, int &r)
    {
        if (!p)
        {
            l = r = 0;
            return;
        }
        if (t[ls].size + 1 <= v)
        {
            l = p;
            split(rs, v - (t[ls].size + 1), rs, r);
        }
        else
        {
            r = p;
            split(ls, v, l, ls);
        }
        pushup(p);
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        if (t[x].rnd < t[y].rnd)
        {
            t[x].r = merge(t[x].r, y);
            pushup(x);
            return x;
        }
        else
        {
            t[y].l = merge(x, t[y].l);
            pushup(y);
            return y;
        }
    }
    int build(int l, int r)
    {
        if (l == r)
            return newnode(a[l]);
        int mid = (l + r) >> 1;
        return merge(build(l, mid), build(mid + 1, r));
    }
    int query(int l, int r)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, l - 1, t1, t2);
        split(t2, r - l + 1, t2, t3);
        int ans = t[t2].sum;
        root = merge(t1, merge(t2, t3));
        return ans;
    }
    void change(int k, int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, k - 1, t1, t2);
        split(t2, 1, t2, t3);
        t[t2].val = v;
        t[t2].sum = t[t2].size * v;
        root = merge(t1, merge(t2, t3));
    }
    void addx(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v, t1, t3);
        t2 = newnode(v);
        root = merge(t1, merge(t2, t3));
    }
    void delet(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v - 1, t1, t2);
        split_v(t2, v, t2, t3);
        t2 = merge(t[t2].l, t[t2].r);
        root = merge(merge(t1, t2), t3);
    }
    int rank(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v - 1, t1, t3);
        int ans = t[t1].size + 1;
        root = merge(t1, t3);
        return ans;
    }
    int query_min(int p)
    {
        while (ls)
        {
            p = ls;
        }
        return t[p].val;
    }
    int query_max(int p)
    {
        while (rs)
        {
            p = rs;
        }
        return t[p].val;
    }
    int ith(int k)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, k, t1, t3);
        int ans = query_max(t1);
        root = merge(t1, t3);
        return ans;
    }
    int get_pre(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v - 1, t1, t3);
        int ans = query_max(t1);
        root = merge(t1, t3);
        return ans;
    }
    int get_nxt(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v, t1, t3);
        int ans = query_min(t3);
        root = merge(t1, t3);
        return ans;
    }
    void dfs(int p)
    {
        if (!p)
            return;
        dfs(ls);
        dfs(rs);
    }
} Tree;

题目

P3369 【模板】普通平衡树

平衡树模板题。

// #pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define ONLINE_JUDGE
// #define MULTI_CASES
#define endl '\n'
const int MaxN = 2e5 + 100;
const int INF = 1e9;
const int mod = 212370440130137957ll;
int T = 1, N, M;
int a[MaxN];
struct FHQ_treap
{
#define ls t[p].l
#define rs t[p].r
    struct Point
    {
        int l, r;
        int val, rnd;
        int size, sum;
    } t[MaxN];
    int tot = 0, root = 0;
    void pushup(int p)
    {
        t[p].size = t[ls].size + t[rs].size + 1;
        t[p].sum = t[ls].sum + t[rs].sum + t[p].val;
    }
    Point pushup(Point now, Point l, Point r)
    {
        now.size = l.size + r.size + 1;
        return now;
    }
    int newnode(int v)
    {
        int p = ++tot;
        t[p].val = t[p].sum = v;
        t[p].l = t[p].r = 0;
        t[p].rnd = rand() * rand();
        t[p].size = 1;
        return p;
    }
    void split_v(int p, int v, int &l, int &r)
    {
        if (!p)
        {
            l = r = 0;
            return;
        }
        if (t[p].val <= v)
        {
            l = p;
            split_v(rs, v, rs, r);
        }
        else
        {
            r = p;
            split_v(ls, v, l, ls);
        }
        pushup(p);
    }
    void split(int p, int v, int &l, int &r)
    {
        if (!p)
        {
            l = r = 0;
            return;
        }
        if (t[ls].size + 1 <= v)
        {
            l = p;
            split(rs, v - (t[ls].size + 1), rs, r);
        }
        else
        {
            r = p;
            split(ls, v, l, ls);
        }
        pushup(p);
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        if (t[x].rnd < t[y].rnd)
        {
            t[x].r = merge(t[x].r, y);
            pushup(x);
            return x;
        }
        else
        {
            t[y].l = merge(x, t[y].l);
            pushup(y);
            return y;
        }
    }
    int build(int l, int r)
    {
        if (l == r)
            return newnode(a[l]);
        int mid = (l + r) >> 1;
        return merge(build(l, mid), build(mid + 1, r));
    }
    int query(int l, int r)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, l - 1, t1, t2);
        split(t2, r - l + 1, t2, t3);
        int ans = t[t2].sum;
        root = merge(t1, merge(t2, t3));
        return ans;
    }
    void change(int k, int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, k - 1, t1, t2);
        split(t2, 1, t2, t3);
        t[t2].val = v;
        t[t2].sum = t[t2].size * v;
        root = merge(t1, merge(t2, t3));
    }
    void addx(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v, t1, t3);
        t2 = newnode(v);
        root = merge(t1, merge(t2, t3));
    }
    void delet(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v - 1, t1, t2);
        split_v(t2, v, t2, t3);
        t2 = merge(t[t2].l, t[t2].r);
        root = merge(merge(t1, t2), t3);
    }
    int rank(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v - 1, t1, t3);
        int ans = t[t1].size + 1;
        root = merge(t1, t3);
        return ans;
    }
    int query_min(int p)
    {
        while (ls)
        {
            p = ls;
        }
        return t[p].val;
    }
    int query_max(int p)
    {
        while (rs)
        {
            p = rs;
        }
        return t[p].val;
    }
    int ith(int k)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, k, t1, t3);
        int ans = query_max(t1);
        root = merge(t1, t3);
        return ans;
    }
    int get_pre(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v - 1, t1, t3);
        int ans = query_max(t1);
        root = merge(t1, t3);
        return ans;
    }
    int get_nxt(int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split_v(root, v, t1, t3);
        int ans = query_min(t3);
        root = merge(t1, t3);
        return ans;
    }
    void dfs(int p)
    {
        if (!p)
            return;
        dfs(ls);
        dfs(rs);
    }
} Tree;
inline void Solve()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1)
            Tree.addx(x);
        if (opt == 2)
            Tree.delet(x);
        if (opt == 3)
            cout << Tree.rank(x) << endl;
        if (opt == 4)
            cout << Tree.ith(x) << endl;
        if (opt == 5)
            cout << Tree.get_pre(x) << endl;
        if (opt == 6)
            cout << Tree.get_nxt(x) << endl;
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    srand(time(0));
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    // fclose(stdin);
    // fclose(stdout);
    return 0;
}

P3391 【模板】文艺平衡树

给定一个序列，然后进行 $m$ 次翻转区间的操作，求最终的序列。$m\le 10^5$

显然此题可以使用 FHQ-Treap 进行区间操作。

题目的核心操作是 reverse(l,r)，即翻转区间 $[l,r]$。显然我们可以考虑将其分裂为 $[1,l-1],[l,r],[r+1,n]$ 三个区间。然后递归交换 $[l,r]$ 区间的左右子树即可。但是显然其时间复杂度 $O(n\times \log_2 n)$ 甚至比不上直接暴力。

考虑优化，我们可以使用线段树中常用的懒标记来优化，对于每次操作，仅翻转当前节点的左右儿子，然后将懒标记分别下传至左右子树。由于翻转两次的结果就相当于没有翻转，所以 rev_tag 可以通过异或来修改。

但是，如果我们调换左右儿子，那么其将不符合 Treap 的性质。

不难发现，此题并没有对权值有任何要求，所以我们分裂的时候可以按照排名来分裂合并，这样的分裂方式不符合 $BST$ 的性质，但可以正确的维护中序遍历。

所有操作之后，中序遍历输出答案即可。

#include <bits/stdc++.h>
using namespace std;
// #define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
const int MaxN = 2e5 + 100;
const int INF = 1e9;
const int mod = 1e9 + 7;
int T = 1, N, M;
int a[MaxN];
struct FHQ_Treap
{
#define ls t[p].l
#define rs t[p].r
    struct Point
    {
        int l, r;
        int val, rnd;
        int rev_tag;
        int siz;
    } t[MaxN];
    int tot = 0, root = 0;
    void pushdown(int p)
    {
        if (t[p].rev_tag)
        {
            swap(ls, rs);
            if (ls)
                t[ls].rev_tag ^= 1;
            if (rs)
                t[rs].rev_tag ^= 1;
            t[p].rev_tag = 0;
        }
    }
    void pushup(int p)
    {
        t[p].siz = t[ls].siz + t[rs].siz + 1;
    }
    void split(int p, int v, int &l, int &r)
    {
        if (!p)
        {
            l = r = 0;
            return;
        }
        pushdown(p);
        if (t[ls].siz + 1 <= v)
        {
            l = p;
            split(rs, v - t[ls].siz - 1, rs, r); // 修改：v 要减去左子树大小和当前节点大小
        }
        else
        {
            r = p;
            split(ls, v, l, ls);
        }
        pushup(p); // 添加：更新节点大小
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        pushdown(x);
        pushdown(y);
        if (t[x].rnd < t[y].rnd)
        {
            t[x].r = merge(t[x].r, y);
            pushup(x);
            return x;
        }
        else
        {
            t[y].l = merge(x, t[y].l);
            pushup(y);
            return y;
        }
    }
    int newnode(int x)
    {
        int p = ++tot;
        t[p].siz = 1;
        t[p].l = t[p].r = 0;
        t[p].rnd = rand() * rand();
        t[p].val = x;
        return p;
    }
    void dfs(int p)
    {
        if (!p)
            return;
        pushdown(p);
        dfs(ls);
        cout << t[p].val << " ";
        dfs(rs);
    }
    void reverse(int l, int r)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, l - 1, t1, t2);
        split(t2, r - l + 1, t2, t3);
        t[t2].rev_tag ^= 1;
        root = merge(t1, merge(t2, t3));
    }
} Tree;
inline void Solve()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        Tree.root = Tree.merge(Tree.root, Tree.newnode(i));
    }
    for (int i = 1; i <= M; i++)
    {
        int l, r;
        cin >> l >> r;
        Tree.reverse(l, r);
    }
    Tree.dfs(Tree.root);
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
    srand(time(0)); // 添加：初始化随机数种子
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}

P2042 [NOI2005] 维护数列

给定的 $6$ 种操作中，$1,2,3,5$ 都是比较常规的操作，关键是操作 $4$：区间翻转和操作 $6$：最大子列和。区间翻转的操作和上题类似，关键还是在于最大子列和。

INSERT

我们可以先把这 $tot$ 个数字建出一棵 Treap，然后与原树分裂合并即可。

DELETE

同理先把这一区间分裂出来，然后删除此区间并将其合并。

MAKE-SAME

如果每次都修改显然时间复杂度过高，所以我们可以使用类似线段树的懒标记来降低复杂度。

REVERSE

区间翻转，思路和上题类似，同样使用一个懒标记来维护。

GET-SUM

区间求和，可以在平衡树中直接维护求和。

MAX-SUM

求最大子列和，考虑分治法，具体流程如下：

不难发现，前两个步骤与其他区间操作并无区别，主要考虑最后一个步骤。

显然，跨区间求和本质上就是左区间的最大后缀和加上右区间的最大前缀和。那么我们只需要对跨区间求和、左区间的最大子段和与右区间的最大子段和比大小求解分治递归即可。

注意一个坑点：最大子列和一定有值，所以在初始化最大子段和的时候要将当前节点的权值作为初始值。

出错点

Code

#include <bits/stdc++.h>
using namespace std;
// #define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
#define troot Tree.root
const int MaxN = 5e5 + 100;
const int INF = 1e9;
const int mod = 1e9 + 7;
int T = 1, N, M;
int a[MaxN];
int st[MaxN];
int tp = 0;
struct FHQ_TREAP
{
#define ls t[p].l
#define rs t[p].r
    struct Point
    {
        int l, r;
        int val, rnd;
        int maxl, maxn, maxr;
        bool rev_tag = 0, cover_tag = 0;
        int sum, siz;
        int cov = 0;
    } t[MaxN];
    int tot = 0, root = 0;
    void pushup(int p)
    {
        if (!p)
            return;

        t[p].siz = t[ls].siz + t[rs].siz + 1;
        t[p].sum = t[ls].sum + t[rs].sum + t[p].val;

        t[p].maxl = max(t[ls].maxl, t[ls].sum + t[p].val + t[rs].maxl);
        t[p].maxl = max(0LL, t[p].maxl);
        t[p].maxr = max(t[rs].maxr, t[rs].sum + t[p].val + t[ls].maxr);
        t[p].maxr = max(0LL, t[p].maxr);

        t[p].maxn = max(t[p].val, t[ls].maxr + t[p].val + t[rs].maxl);
        if (ls)
            t[p].maxn = max(t[p].maxn, t[ls].maxn);
        if (rs)
            t[p].maxn = max(t[p].maxn, t[rs].maxn);
        // t[p].maxn = max(t[p].val, t[p].sum);
    }
    void reverse(int p)
    {
        if (!p)
            return;
        swap(t[p].l, t[p].r);
        t[p].rev_tag ^= 1;
        swap(t[p].maxr, t[p].maxl);
    }
    void cover(int p, int k)
    {
        if (!p)
            return;
        t[p].cov = k;
        t[p].cover_tag = 1;
        t[p].val = k;
        t[p].sum = t[p].siz * k;
        t[p].maxn = max(t[p].sum, k);
        t[p].maxl = t[p].maxr = max(0LL, t[p].sum);
    }
    void pushdown(int p)
    {
        if (!p)
        {
            return;
        }
        if (t[p].rev_tag)
        {
            if (ls)
                reverse(ls);
            if (rs)
                reverse(rs);
            t[p].rev_tag = 0;
        }
        if (t[p].cover_tag)
        {
            if (ls)
                cover(ls, t[p].cov);
            if (rs)
                cover(rs, t[p].cov);
            t[p].cover_tag = t[p].cov = 0;
        }
    }
    int newnode(int v)
    {
        int p = st[tp--];
        t[p].val = t[p].sum = v;
        t[p].l = t[p].r = 0;
        t[p].rnd = rand() * rand();
        t[p].siz = 1;
        t[p].maxl = t[p].maxr = max(0LL, v);
        t[p].maxn = v;
        t[p].cover_tag = t[p].rev_tag = 0;
        return p;
    }
    void split(int p, int v, int &l, int &r)
    {
        if (!p)
        {
            l = r = 0;
            return;
        }
        pushdown(p);
        if (t[ls].siz + 1 <= v)
        {
            l = p;
            split(rs, v - (t[ls].siz + 1), rs, r);
        }
        else
        {
            r = p;
            split(ls, v, l, ls);
        }
        pushup(p);
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        if (t[x].rnd < t[y].rnd)
        {
            pushdown(x);
            t[x].r = merge(t[x].r, y);
            pushup(x);
            return x;
        }
        else
        {
            pushdown(y);
            t[y].l = merge(x, t[y].l);
            pushup(y);
            return y;
        }
    }
    int build(int l, int r)
    {
        if (l == r)
            return newnode(a[l]);
        int mid = (l + r) >> 1;
        return merge(build(l, mid), build(mid + 1, r));
    }
    int build2(int l, int r, vi &a) // 传递引用避免拷贝
    {
        if (l == r)
            return newnode(a[l]);
        int mid = (l + r) >> 1;
        return merge(build2(l, mid, a), build2(mid + 1, r, a));
    }
    void delet(int p)
    {
        if (!p)
            return;
        st[++tp] = p;
        if (ls)
            delet(ls);
        if (rs)
            delet(rs);
    }
    void make_same(int posi, int tot, int c)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, posi - 1, t1, t2);
        split(t2, tot, t2, t3);
        cover(t2, c);
        root = merge(t1, merge(t2, t3));
    }
    void reverse(int posi, int tot)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, posi - 1, t1, t2);
        split(t2, tot, t2, t3);
        reverse(t2);
        root = merge(t1, merge(t2, t3));
    }
    int get_sum(int posi, int tot)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, posi - 1, t1, t2);
        split(t2, tot, t2, t3);
        // pushdown()
        int sum = t[t2].sum;
        root = merge(t1, merge(t2, t3));
        return sum;
    }
    int max_sum()
    {
        // pushup(root);
        return t[root].maxn;
    }
} Tree;
inline void Solve()
{
    cin >> N >> M;
    for (int i = 1; i <= 500000; i++)
        st[++tp] = i;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
    }
    troot = Tree.merge(troot, Tree.build(1, N));
    for (int i = 1; i <= M; i++)
    {
        string s;
        cin >> s;
        if (s == "INSERT")
        {
            int posi, tot;
            vi c;
            cin >> posi >> tot;
            int t1 = 0, t2 = 0;
            Tree.split(troot, posi, t1, t2);
            c.push_back(0);
            for (int j = 1; j <= tot; j++)
            {
                int x;
                cin >> x;
                c.push_back(x);
            }
            troot = Tree.merge(t1, Tree.merge(Tree.build2(1, tot, c), t2));
        }
        if (s == "DELETE")
        {
            int posi, tot;
            cin >> posi >> tot;
            int t1 = 0, t2 = 0, t3 = 0;
            Tree.split(troot, posi - 1, t1, t2);
            Tree.split(t2, tot, t2, t3);
            Tree.delet(t2);
            // t2 = merge(t[t2].l, t[t2].r);
            troot = Tree.merge(t1, t3);
        }
        if (s == "MAKE-SAME")
        {
            int posi, tot, k;
            cin >> posi >> tot >> k;
            Tree.make_same(posi, tot, k);
        }
        if (s == "REVERSE")
        {
            int posi, tot;
            cin >> posi >> tot;
            Tree.reverse(posi, tot);
        }
        if (s == "GET-SUM")
        {
            int posi, tot;
            cin >> posi >> tot;
            cout << Tree.get_sum(posi, tot) << endl;
        }
        if (s == "MAX-SUM")
        {
            cout << Tree.max_sum() << endl;
        }
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}

P3278 [SCOI2013] 多项式的运算

题目总共 $4$ 种操作：

操作 $1,2$：区间加和区间乘。

操作 $3$：区间右移 $1$ 位。

操作 $4$：代入求值。

显然我们可以使用 Fhq-Treap 来维护。

首先对于操作 $1,2$，我们可以将区间 $[l,r]$ 分裂出来，然后对其进行操作即可，这里使用类似线段树的两个懒标记来维护即可。

对于操作 $4$，由于其次数不超过 $10$ 次，可以直接 $dfs$ 维护出中序遍历暴力求解即可。

对于操作 $3$，我们可以将区间拆分为 $[1,l-1],[l,r-1],[r],[r+1],[r+2,N]$，然后只需要将 $0$ 插到区间 $1、2$ 之间，然后将 $[r]$ 合并到 $[r+1]$。之后全部合并起来即可。

#include <bits/stdc++.h>
using namespace std;
// #define MULTI_CASES
#define ll long long
#define int ll
#define endl '\n'
#define vi vector<int>
#define PII pair<int, int>
const int MaxN = 5e5 + 100;
const int INF = 1e9;
const int mod = 20130426;
int T = 1, N, M;
int a[MaxN];
int ans, tmp, V;
int st[MaxN], tp = 0;
struct FHQ_TREAP
{
#define ls t[p].l
#define rs t[p].r
    struct Point
    {
        int l, r;
        int val, rnd;
        int tag, mul;
        int siz;
    } t[MaxN];
    int tot = 0, root = 0;
    int newnode(int v)
    {
        int p = ++tot;
        t[p].l = t[p].r = 0;
        t[p].rnd = rand() * rand();
        t[p].val = v % mod;
        t[p].tag = 0;
        t[p].mul = 1;
        t[p].siz = 1;
        return p;
    }
    void pushup(int p)
    {
        t[p].siz = t[ls].siz + t[rs].siz + 1;
    }
    void mul(int p, int v)
    {
        (t[p].val *= v) %= mod;
        (t[p].mul *= v) %= mod;
        (t[p].tag *= v) %= mod;
    }
    void add(int p, int v)
    {
        (t[p].val += v) %= mod;
        (t[p].tag += v) %= mod;
    }
    void pushdown(int p)
    {
        if (t[p].mul != 1)
        {
            if (ls)
                mul(ls, t[p].mul);
            if (rs)
                mul(rs, t[p].mul);
            t[p].mul = 1;
        }
        if (t[p].tag)
        {
            if (ls)
                add(ls, t[p].tag);
            if (rs)
                add(rs, t[p].tag);
            t[p].tag = 0;
        }
        }
    void split(int p, int v, int &l, int &r)
    {
        if (!p)
        {
            l = r = 0;
            return;
        }
        pushdown(p);
        if (t[ls].siz + 1 <= v)
        {
            l = p;
            split(rs, v - (t[ls].siz + 1), rs, r);
        }
        else
        {
            r = p;
            split(ls, v, l, ls);
        }
        pushup(p);
    }
    int merge(int x, int y)
    {
        if (!x || !y)
            return x + y;
        if (t[x].rnd < t[y].rnd)
        {
            pushdown(x);
            t[x].r = merge(t[x].r, y);
            pushup(x);
            return x;
        }
        else
        {
            pushdown(y);
            t[y].l = merge(x, t[y].l);
            pushup(y);
            return y;
        }
    }
    void dfs(int p)
    {
        if (!p)
            return;
        pushdown(p);
        if (ls)
            dfs(ls);
        // cerr << t[p].val << " ";
        ans = (ans + (tmp * t[p].val)) % mod;
        tmp = (tmp * V) % mod;
        if (rs)
            dfs(rs);
    }
    void add(int l, int r, int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, l - 1, t1, t2);
        split(t2, r - l + 1, t2, t3);
        add(t2, v);
        // debug(t2);
        root = merge(t1, merge(t2, t3));
    }
    // void clear(int p)
    // {
    //     if (!p)
    //         return;
    //     st[++tp] = p;
    //     if (ls)
    //         clear(ls);
    //     if (rs)
    //         clear(rs);
    // }
    void mul(int l, int r, int v)
    {
        int t1 = 0, t2 = 0, t3 = 0;
        split(root, l - 1, t1, t2);
        split(t2, r - l + 1, t2, t3);
        mul(t2, v);
        root = merge(t1, merge(t2, t3));
    }
    void mulx(int l, int r)
    {
        int t1 = 0, t2 = 0, t3 = 0, t4 = 0, t5 = 0;
        split(root, l - 1, t1, t2);
        split(t2, r - l, t2, t3);
        split(t3, 1, t3, t4);
        split(t4, 1, t4, t5);
        int newt = newnode(0);
        (t[t4].val += t[t3].val) %= mod;
        root = merge(t1, merge(newt, merge(t2, merge(t4, t5))));
        // clear(t3);
    }
    void debug(int p)
    {
        cerr << t[p].val << " " << t[p].tag << " " << t[p].l << " " << t[p].r << endl;
    }
} Tree;
inline void Solve()
{
    cin >> N;

    for (int i = 0; i <= 100005; i++)
    {
        Tree.root = Tree.merge(Tree.root, Tree.newnode(0));
    }
    for (int i = 1; i <= N; i++)
    {
        string s;
        cin >> s;
        if (s == "add")
        {
            int l, r, v;
            cin >> l >> r >> v;
            l++, r++;
            Tree.add(l, r, v);
        }
        if (s == "mul")
        {
            int l, r, v;
            cin >> l >> r >> v;
            l++, r++;
            Tree.mul(l, r, v);
        }
        if (s == "mulx")
        {
            int l, r;
            cin >> l >> r;
            l++, r++;
            Tree.mulx(l, r);
        }
        if (s == "query")
        {
            cin >> V;
            ans = 0, tmp = 1;
            Tree.dfs(Tree.root);
            // cerr << endl;
            cout << ans << endl;
        }
    }
}
signed main()
{
#ifndef ONLINE_JUDGE
    freopen(".in", "r", stdin);
    freopen(".out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(nullptr), cout.tie(nullptr);
    srand(time(0));
#ifdef MULTI_CASES
    cin >> T;
    while (T--)
#endif
        Solve();
    return 0;
}

本文采用 CC BY-NC 4.0 许可协议，转载请注明出处并保持非商业用途。