浅谈 FHQ Treap

kaikai_qwq · 2026-08-15 14:42:06 · 算法·理论

请确保你已经学会二叉搜索树（BST）。

主要讲解序列平衡树（普通平衡树可以使用值域线段树之类的替代）。

由于本人是小升区 xxs，数据结构学的不多，文章有错误还请多多谅解。

无旋 Treap/FHQ Treap

FHQ Treap 的每个节点都有一个随机优先级。

FHQ Treap 满足二叉搜索树和堆的性质，即：

对于树中的任意一个节点，其左子树中所有节点的权值都小于该节点的权值；其右子树中所有节点的权值都大于该节点的权值。
整棵树必须满足父节点的优先级大于（或小于）子节点的优先级。

我们以一道例题（模板题）入手：

【模板】文艺平衡树

维护一个长度为 n 的序列，有 m 次操作，每次操作为翻转一个区间 [l, r]，求出所有操作后的序列。

在这题，对于每个节点，我们需要维护：子树大小，节点权值，左右儿子，优先级，翻转标记。

struct node {
    int ls, rs;
    int key, pri;
    int siz, lzy;
} t[MAXN];
//新建一个权值为 x 的节点
void new_node(int x) {
    cnt++;
    t[cnt].siz = 1;
    t[cnt].ls = t[cnt].rs = 0;
    t[cnt].key = x;
    t[cnt].pri = rand();
}
//合并两个子树的信息。
void pushup(int u) {
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
}
void pushdown(int u) {
    if (t[u].lzy) {
        //翻转相当于交换左右儿子
        swap(t[u].ls, t[u].rs);
        t[t[u].ls].lzy ^= 1, t[t[u].rs].lzy ^= 1;
        t[u].lzy = 0;
    }
}

FHQ Treap 处理序列的思想为：

将操作区间 [l, r] 从整个区间中分裂出去。
对分裂出的 [l, r] 进行操作。
将 [l, r] 合并回整个序列：

分裂操作

我们需要分裂出一个区间 [l, r]，可以考虑将 [l, n] 从整个区间分裂出去，然后从 [l, n] 中分裂出 [l, r]。

那么，考虑如何从一个完整的区间（子树）u 中的节点前 k 个放在 L 中，其余放在 R。

分裂过程：

当前遍历到了 u 这个节点：

若左子树加上 u 这个节点这些的大小（即左子树子树大小加一）\le k，说明当前节点包括左子树都给 L，然后将 k 减去对应大小分裂右子树。
否则，给 R，分裂左子树。

::::info[时间复杂度证明] 对于最坏情况，因为每次只会递归一个方向，显然是递归深度等于从根到叶的最长路径长度，也就是树高 h，所以复杂度是 O(h) 的。 ::::

void split(int u, int x, int &l, int &r) {
    if (u == 0) {
        l = r = 0;
        return;
    }
    pushdown(u);
    if (t[t[u].ls].siz + 1 <= x) {
        l = u;
        split(t[u].rs, x - t[t[u].ls].siz - 1, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}

合并操作

当我们更新完一个区间 [l, r]，需要合并到原来的子树。

合并是分裂的逆操作，我们合并后需要满足二叉搜索树和堆的性质。

那么，考虑当前应该谁接在谁下面。

若 L 的优先级 < R 的，则 L 成为根结点，由于 R 的权值 \ge L，所以 R 和 L 的右子树合并。
否则，R 成为根节点，R 和 L 左子树合并。

::::info[时间复杂度证明] 和 merge 一样，每次往一个方向递归，最多递归树高 h 次，所以复杂度也是 O(h)。 ::::

int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    if (t[l].pri < t[r].pri) {
        pushdown(l);
        t[l].rs = merge(t[l].rs, r);
        pushup(l);
        return l;
    } else {
        pushdown(r);
        t[r].ls = merge(l, t[r].ls);
        pushup(r);
        return r;
    }
}

回到这一题，修改一个区间直接分裂出来打上翻转标记即可：

int l, r, p;
split(root, y, l, r);
split(l, x - 1, l, p);
t[p].lzy ^= 1;
root = merge(merge(l, p), r);

::::info[复杂度证明] 空间复杂度显然是 O(n) 的。

FHQ Treap 的形态等价于将节点按优先级排序后依次插入 BST 得到的形态，而由于优先级随机，且随机插入 BST 的期望树高为 O(\log n)，所以 FHQ Treap 期望树高为 O(\log n)。

对于一次操作，只需要 O(1) 次 split 和 merge 和 O(1) 的修改，由于 split 和 merge 操作复杂度是 O(h)，而树高期望 O(\log n)，所以复杂度是 O(\log n)。

设 n, m 同阶，那么总复杂度为 O(n\log n)。

::::success[完整代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e6 + 10;
int cnt, root;
struct node {
    int ls, rs;
    int key, pri;
    int siz, lzy;
} t[MAXN];
void new_node(int x) {
    cnt++;
    t[cnt].siz = 1;
    t[cnt].ls = t[cnt].rs = 0;
    t[cnt].key = x;
    t[cnt].pri = rand();
}
void pushup(int u) {
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
}
void pushdown(int u) {
    if (t[u].lzy) {
        swap(t[u].ls, t[u].rs);
        t[t[u].ls].lzy ^= 1, t[t[u].rs].lzy ^= 1;
        t[u].lzy = 0;
    }
}
void split(int u, int x, int &l, int &r) {
    if (u == 0) {
        l = r = 0;
        return;
    }
    pushdown(u);
    if (t[t[u].ls].siz + 1 <= x) {
        l = u;
        split(t[u].rs, x - t[t[u].ls].siz - 1, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    if (t[l].pri < t[r].pri) {
        pushdown(l);
        t[l].rs = merge(t[l].rs, r);
        pushup(l);
        return l;
    } else {
        pushdown(r);
        t[r].ls = merge(l, t[r].ls);
        pushup(r);
        return r;
    }
}
void out(int u) {
    if (u == 0) return;
    pushdown(u);
    out(t[u].ls);
    cout << t[u].key << ' ';
    out(t[u].rs);
}
signed main() {
    srand(time(0));
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        new_node(i);
        root = merge(root, cnt);
    }
    while (m--) {
        int x, y;
        cin >> x >> y;
        int l, r, p;
        split(root, y, l, r);
        split(l, x - 1, l, p);
        t[p].lzy ^= 1;
        root = merge(merge(l, p), r);
    }
    out(root);
    return 0;
}

::::

可持久化 FHQ Treap

【模板】可持久化文艺平衡树

您需要写一种数据结构，来维护一个序列，其中需要提供以下操作（对于各个以往的历史版本）：

在第 p 个数后插入数 x。

删除第 p 个数。

翻转区间 [l,r]，例如原序列是 \{5,4,3,2,1\}，翻转区间 [2,4] 后，结果是 \{5,2,3,4,1\}。

查询区间 [l,r] 中所有数的和。

和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 4 即保持原版本无变化），新版本即编号为此次操作的序号。

对于 1, 2 操作，分裂出来，在丢弃/加入一个节点再合并回去即可；对于 4 操作，平衡树每个节点维护子树和，把区间分裂出来输出这个和即可。

其实和普通的 FHQ Treap 区别就是：后面的操作不能影响到前面的节点，于是当一个节点发生改变时，要将自己复制一遍。

对于每个版本，需要独立记录一个根节点。

int copy_node(int u) {
    t[++cnt] = t[u];
    return cnt;
}

在分裂与合并时，根节点发生了改变，需要将当前根节点复制一遍。

void split(int u, int x, int &l, int &r) {
    if (u == 0) {
        l = r = 0;
        return;
    }
    u = copy_node(u);
    pushdown(u);
    if (t[t[u].ls].siz + 1 <= x) {
        l = u;
        split(t[u].rs, x - t[t[u].ls].siz - 1, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    pushdown(l), pushdown(r);
    if (t[l].pri < t[r].pri) {
        int x = copy_node(l);
        t[x].rs = merge(t[x].rs, r);
        pushup(x);
        return x;
    } else {
        int x = copy_node(r);
        t[x].ls = merge(l, t[x].ls);
        pushup(x);
        return x;
    }
}

::::info[复杂度证明] 对于时间复杂度，由于 split 和 merge 只是多进行了 O(1) 的复制节点，所以复杂度还是 O(\log n)，总复杂度还是 O(n\log n)。

由于 split 和 merge 最多递归 O(\log n) 次，每次操作进行 O(1) 次 split 和 merge，总共复制 O(\log n) 个节点，所以单次操作空间复杂度为 O(\log n)。

那么总空间复杂度为 O(n + m\log n)。

::::success[完整代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e7 + 10;
int n;
int root[MAXN], cnt;
struct node {
    int ls, rs;
    int key, pri;
    int siz, sum;
    int lzy;
} t[MAXN];
int new_node(int x) {
    t[++cnt].ls = 0;
    t[cnt].rs = 0;
    t[cnt].key = x, t[cnt].pri = rand();
    t[cnt].siz = 1;
    t[cnt].sum = x;
    t[cnt].lzy = 0;
    return cnt;
}
void pushup(int u) {
    t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + t[u].key;
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
}
int copy_node(int u) {
    t[++cnt] = t[u];
    return cnt;
} 
void pushdown(int u) {
    if (t[u].lzy) {
        if (t[u].ls) {
            t[u].ls = copy_node(t[u].ls);
            t[t[u].ls].lzy ^= 1; 
        }
        if (t[u].rs) {
            t[u].rs = copy_node(t[u].rs);
            t[t[u].rs].lzy ^= 1;
        }
        swap(t[u].ls, t[u].rs);  
        t[u].lzy = 0;
    }
}
void split(int u, int x, int &l, int &r) {
    if (u == 0) {
        l = r = 0;
        return;
    }
    u = copy_node(u);
    pushdown(u);
    if (t[t[u].ls].siz + 1 <= x) {
        l = u;
        split(t[u].rs, x - t[t[u].ls].siz - 1, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    pushdown(l), pushdown(r);
    if (t[l].pri < t[r].pri) {
        int x = copy_node(l);
        t[x].rs = merge(t[x].rs, r);
        pushup(x);
        return x;
    } else {
        int x = copy_node(r);
        t[x].ls = merge(l, t[x].ls);
        pushup(x);
        return x;
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    srand(time(0));
    cin >> n;
    int last = 0;
    for (int i = 1; i <= n; i++) {
        int v, op;
        cin >> v >> op;
        int p, x, l, r;
        if (op == 1) {
            cin >> p >> x;
            p ^= last;
            x ^= last;
            int a, b;
            split(root[v], p, a, b);
            root[i] = merge(merge(a, new_node(x)), b);
        } else if (op == 2) {
            cin >> p;
            p ^= last;
            int a, b, c;
            split(root[v], p - 1, a, b);
            split(b, 1, b, c);
            root[i] = merge(a, c);
        } else if (op == 3) {
            cin >> l >> r;
            l ^= last;
            r ^= last;
            int a, b, c;
            split(root[v], l - 1, a, b);
            split(b, r - l + 1, b, c);
            b = copy_node(b);
            t[b].lzy ^= 1;
            root[i] = merge(merge(a, b), c);
        } else if (op == 4) {
            cin >> l >> r;
            l ^= last;
            r ^= last;
            int a, b, c;
            split(root[v], l - 1, a, b);
            split(b, r - l + 1, b, c);
            last = t[b].sum;
            cout << last << '\n';
            root[i] = merge(merge(a, b), c);
        }
    }
    return 0;
}

::::

例题

P2042 [NOI2005] 维护数列

请写一个程序，要求维护一个数列，支持以下 6 种操作：

编号	名称	格式	说明
1	插入	\operatorname{INSERT}\ posi \ tot \ c_1 \ c_2 \cdots c_{tot}	在当前数列的第 posi 个数字后插入 tot 个数字：c_1, c_2 \cdots c_{tot}；若在数列首插入，则 posi 为 0
2	删除	\operatorname{DELETE} \ posi \ tot	从当前数列的第 posi 个数字开始连续删除 tot 个数字
3	修改	\operatorname{MAKE-SAME} \ posi \ tot \ c	从当前数列的第 posi 个数字开始的连续 tot 个数字统一修改为 c
4	翻转	\operatorname{REVERSE} \ posi \ tot	取出从当前数列的第 posi 个数字开始的 tot 个数字，翻转后放入原来的位置
5	求和	\operatorname{GET-SUM} \ posi \ tot	计算从当前数列的第 posi 个数字开始的 tot 个数字的和并输出
6	求最大子串和	\operatorname{MAX-SUM}	求出当前数列中和最大的一段非空子串，并输出最大和

考察你是否理解平衡树。

对于每个位置，除了平衡树基本信息，维护翻转标记，子树和，子树最大前缀和，最大后缀和，最大子段和，赋值标记，合并左右儿子信息和小白逛公园一样，注意最大子段和不能为空。

这题需要垃圾回收。

注意下传标记时的顺序，需要先下传赋值标记，再下传翻转标记。

::::success[code]

struct node {
    int ls, rs;
    int key, pri;
    int siz, lzy;
    int sum, maxl, maxr, Max;
    int fz;
} t[MAXN];
int st[MAXN], top;
//垃圾回收
int new_node(int x) {
    cnt = st[top--];
    t[cnt].siz = 1;
    t[cnt].ls = t[cnt].rs = t[cnt].lzy = 0;
    t[cnt].key = t[cnt].sum = x;
    t[cnt].maxl = t[cnt].maxr = max(0ll, x);
    t[cnt].Max = x;
    t[cnt].pri = rand();
    t[cnt].fz = -inf;
    return cnt;
}
void pushup(int u) {
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
    t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + t[u].key;
    t[u].maxl = max(0ll, max(t[t[u].ls].maxl, t[t[u].ls].sum + t[u].key + t[t[u].rs].maxl));
    t[u].maxr = max(0ll, max(t[t[u].rs].maxr, t[t[u].rs].sum + t[u].key + t[t[u].ls].maxr));
    t[u].Max = max(t[u].key, t[u].key + t[t[u].ls].maxr + t[t[u].rs].maxl);
    if (t[u].ls) t[u].Max = max(t[u].Max, t[t[u].ls].Max);
    if (t[u].rs) t[u].Max = max(t[u].Max, t[t[u].rs].Max);
}
void reverse(int u) {
    swap(t[u].ls, t[u].rs);
    swap(t[u].maxl, t[u].maxr);
    t[u].lzy ^= 1;
}
void cover(int u, int s) {
    t[u].key = t[u].fz = s;
    t[u].sum = t[u].siz * s;
    t[u].lzy = 0;
    if (s < 0) {
        t[u].maxl = t[u].maxr = 0;
        t[u].Max = s;
    } else t[u].maxl = t[u].maxr = t[u].Max = t[u].sum;
}
void pushdown(int u) {
    if (t[u].fz != -inf) {
        cover(t[u].ls, t[u].fz);
        cover(t[u].rs, t[u].fz);
        t[u].fz = -inf;
        t[u].lzy = 0;
    }
    if (t[u].lzy) {
        reverse(t[u].ls);
        reverse(t[u].rs);
        t[u].lzy = 0;
    }
}

::::

主要操作部分也是简单的。

::::success[code]

if (op == "INSERT") {
    cin >> posi >> tot >> c;
    int l, r;
    split(root, posi, l, r);
    int u = new_node(c);
    while (--tot) {
        cin >> c;
        u = merge(u, new_node(c));
    } 
    root = merge(merge(l, u), r);
} else if (op == "DELETE") {
    cin >> posi >> tot;
    int l, r, p;
    split(root, posi - 1, l, r);
    split(r, tot, r, p);
    erase(r);
    root = merge(l, p);
} else if (op == "MAKE-SAME") {
    cin >> posi >> tot >> c;
    int l, r, p;
    split(root, posi - 1, l, r);
    split(r, tot, r, p);
    cover(r, c);
    root = merge(merge(l, r), p);
} else if (op == "REVERSE") {
    cin >> posi >> tot;
    int l, r, p;
    split(root, posi - 1, l, r);
    split(r, tot, r, p);
    reverse(r);
    root = merge(merge(l, r), p);
} else if (op == "GET-SUM") {
    cin >> posi >> tot;
    int l, r, p;
    split(root, posi - 1, l, r);
    split(r, tot, r, p);
    cout << t[r].sum << '\n';
    root = merge(merge(l, r), p);
} else if (op == "MAX-SUM") cout << t[root].Max << '\n';

::::

完整代码就不放了。

P4036 [JSOI2008] 火星人

定义了一个函数 \operatorname{LCQ}(x, y)，表示：该字符串中第 x 个字符开始的字串，与该字符串中第 y 个字符开始的字串，两个字串的公共前缀的长度。比方说。你需要对一个字符串做以下操作：

询问。语法：Q x y，x, y 均为正整数。功能：计算 LCQ(x,y)。限制：1 \le x, y \le 当前字符串长度。

修改。语法：R x d，x 是正整数，d 是字符。功能：将字符串中第 x 个字符修改为字符 d。限制：x 不超过当前字符串长度。

插入：语法：I x d，x 是非负整数，d 是字符。功能：在字符串第 x 个字符之后插入字符 d，如果 x=0，则在字符串开头插入。限制：x 不超过当前字符串长度。

对于修改和插入操作，显然是平衡树，于是考虑使用 FHQ Treap 维护。

考虑怎么进行查询操作。

我们可以考虑二分长度，然后使用 Hash 判断是否相等，于是考虑平衡树维护字数哈希值。

考虑怎么维护子树哈希值。

对于左儿子的子树哈希值，显然可以直接加过来；对于当前节点的哈希值，由于需要接在左子树后面，所以为 val\times base^{siz_{l}}，其中 siz 表示子树大小；那么，对于右子树，哈希值为 sum\times base^{siz_{l} + 1}。

::::success[pushup code]

void pushup(int u) {
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
    t[u].sum = t[t[u].ls].sum + t[u].key * B[t[t[u].ls].siz] + t[t[u].rs].sum * B[t[t[u].ls].siz + 1];
}

::::

::::success[完整代码]

//我是使用的自然溢出哈希
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int MAXN = 2e6 + 10;
const int base = 137;
int n, m;
int cnt, root;
struct node {
    int ls, rs;
    int pri;
    int siz, lzy;
    ull sum, key;
} t[MAXN];
ull B[MAXN];
int new_node(ull x) {
    cnt++;
    t[cnt].siz = 1;
    t[cnt].ls = t[cnt].rs = 0;
    t[cnt].key = t[cnt].sum = x;
    t[cnt].pri = rand();
    return cnt;
}
void pushup(int u) {
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
    t[u].sum = t[t[u].ls].sum + t[u].key * B[t[t[u].ls].siz] + t[t[u].rs].sum * B[t[t[u].ls].siz + 1];
}
void split(int u, int x, int &l, int &r) {
    if (u == 0) {
        l = r = 0;
        return;
    }
    if (t[t[u].ls].siz + 1 <= x) {
        l = u;
        split(t[u].rs, x - t[t[u].ls].siz - 1, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    if (t[l].pri > t[r].pri) {
        t[l].rs = merge(t[l].rs, r);
        pushup(l);
        return l;
    } else {
        t[r].ls = merge(l, t[r].ls);
        pushup(r);
        return r;
    }
}
ull query(int x, int k) {
    int l, r, p;
    split(root, x - 1, l, r);
    split(r, k, r, p);
    ull res = t[r].sum;
    root = merge(merge(l, r), p);
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    srand(time(0));
    B[0] = 1;
    for (int i = 1; i <= 1000000; i++) B[i] = B[i - 1] * base;
    string s;
    cin >> s;
    n = s.size();
    s = ' ' + s; 
    for (int i = 1; i <= n; i++) root = merge(root, new_node(s[i] - 'a' + 1));
    cin >> m;
    while (m--) {
        char op;
        cin >> op;
        int x, y;
        cin >> x;
        if (op == 'Q') {
            cin >> y;
            int l = 0, r = min(n - x + 1, n - y + 1);
            while (l <= r) {
                int mid = (l + r) >> 1;
                if (query(x, mid) == query(y, mid)) l = mid + 1;
                else r = mid - 1;
            }
            cout << r << '\n';
        } else if (op == 'R') {
            char c;
            cin >> c;
            int qwq = c - 'a' + 1;
            int l, r, p;
            split(root, x - 1, l, r);
            split(r, 1, r, p);
            t[r].key = qwq;
            pushup(r);
            root = merge(merge(l, r), p);
        } else if (op == 'I') {
            char c;
            cin >> c;
            int qwq = c - 'a' + 1;
            int l, r;
            n++;    
            split(root, x, l, r);
            root = merge(l, merge(new_node(qwq), r));
        }
    }
    return 0;
}

::::

P3215 [HNOI2011] 括号修复 / [JSOI2011] 括号序列

一个合法的括号序列是这样定义的：

空串是合法的。

如果字符串 S 是合法的，则 (S) 也是合法的。

如果字符串 A 和 B 是合法的，则 AB 也是合法的。

现在给你一个长度为 n 的由 ( 和 ) 组成的字符串，位置标号从 1 到 n。对这个字符串有下列四种操作：

Replace a b c：将 [a,b] 之间的所有括号改成 c。假设原来的字符串为：))())())(，那么执行操作 Replace 2 7 ( 后原来的字符串变为：)(((((()(。

Swap a b：将 [a,b] 之间的字符串翻转。假设原来的字符串为：))())())(，那么执行操作 Swap 3 5 后原来的字符串变为：))))(())(。

Invert a b：将 [a,b] 之间的 ( 变成 )，) 变成 (。假设原来的字符串为：))())())(，那么执行操作 Invert 4 8 后原来的字符串变为：))((()(((。

Query a b：询问 [a,b] 之间的字符串至少要改变多少位才能变成合法的括号序列。改变某位是指将该位的 ( 变成 ) 或 ) 变成 (。注意执行操作 Query 并不改变当前的括号序列。假设原来的字符串为：))())())(，那么执行操作 Query 3 6 的结果为 2，因为要将位置 5 的 ) 变成 ( 并将位置 6 的 ( 变成 )。

首先，考虑查询操作怎么做。

我们把 \texttt{(} 看成 -1，\texttt{)} 看成 1。

那么，一个括号串合法的条件为：

总和为 0。
前缀和都 \le 0。
后缀和都 \ge 0。

我们令 \text{premax} 表示前缀和最大值，\text{sufmin} 表示后缀和最小值。

每次把一个 \texttt{)} 改成 \texttt{(}，所有后续前缀和都减少 2，所以 \text{premax} 减少 2。

由于 \text{sufmin} 是负的，取绝对值后变后缀左括号比右括号多了多少个。

每次把一个 \texttt{(} 改成 \texttt{)}，所有前驱后缀和绝对值都减少 2。

那么，可推出一个区间最少要改多少次才能合法的公式为：

\lceil \frac{\text{premax}}{2} \rceil+\lceil \frac{|\text{sufmin}|}{2} \rceil

于是，FHQ Treap 维护子树和，前缀和最大、最小，后缀和最大、最小，以及三种标记。

对于区间取反，前缀和最大需要变成负的前缀和最小，其他同理；另外两个修改是简单的。

对于标记顺序，为取反、赋值、翻转。

::::success[code]

struct node {
    int ls, rs;
    int key, pri;
    int siz, sum;
    int fz, lzy, qf;
    int pm, pi, sm, si;//前缀最大、最小，后缀最大、最小 
} t[MAXN];
int new_node(int x) {
    t[++cnt].siz = 1;
    t[cnt].ls = t[cnt].rs = t[cnt].lzy = t[cnt].qf = 0;
    t[cnt].fz = 0;
    t[cnt].key = t[cnt].sum = x;
    t[cnt].pri = rand();
    t[cnt].pm = t[cnt].pi = t[cnt].sm = t[cnt].si = 0;
    if (x == 1) t[cnt].pm = t[cnt].sm = 1;
    else t[cnt].pi = t[cnt].si = -1;
    return cnt;
} 
void pushup(int u) {
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
    t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + t[u].key;
    t[u].pm = max(t[t[u].ls].pm, t[t[u].ls].sum + t[u].key + t[t[u].rs].pm);
    t[u].pi = min(t[t[u].ls].pi, t[t[u].ls].sum + t[u].key + t[t[u].rs].pi);
    t[u].sm = max(t[t[u].rs].sm, t[t[u].rs].sum + t[u].key + t[t[u].ls].sm);
    t[u].si = min(t[t[u].rs].si, t[t[u].rs].sum + t[u].key + t[t[u].ls].si);
}
void reverse(int u) {
    if (u == 0) return;
    swap(t[u].ls, t[u].rs);
    swap(t[u].pm, t[u].sm);
    swap(t[u].pi, t[u].si);
    t[u].lzy ^= 1;
}
void cover(int u, int s) {
    if (u == 0) return;
    t[u].key = t[u].fz = s;
    t[u].sum = t[u].siz * s;
    // t[u].lzy = t[u].qf = 0;
    if (s == 1) {
        t[u].pm = t[u].sm = t[u].sum;
        t[u].pi = t[u].si = 0;
    } else {
        t[u].pm = t[u].sm = 0;
        t[u].pi = t[u].si = t[u].sum;
    }
}
void qwq(int u) {
    if (u == 0) return;
    t[u].sum *= -1, t[u].key *= -1;
    t[u].qf ^= 1;
    t[u].fz *= -1;
    int x = t[u].pm, y = t[u].pi;
    t[u].pm = -y, t[u].pi = -x;
    x = t[u].sm, y = t[u].si;
    t[u].sm = -y, t[u].si = -x;
}
void pushdown(int u) {
    if (u == 0) return;
    if (t[u].qf) {
        if (t[u].ls) qwq(t[u].ls);
        if (t[u].rs) qwq(t[u].rs);
        t[u].qf = 0;
    }
    if (t[u].fz) {
        if (t[u].ls) cover(t[u].ls, t[u].fz);
        if (t[u].rs) cover(t[u].rs, t[u].fz);
        t[u].fz = 0;
    }
    if (t[u].lzy) {
        if (t[u].ls) reverse(t[u].ls);
        if (t[u].rs) reverse(t[u].rs);
        t[u].lzy = 0;
    }
}

::::

::::success[完整代码]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 4e6 + 10;
const int inf = 1e18;
int cnt, root;
struct node {
    int ls, rs;
    int key, pri;
    int siz, sum;
    int fz, lzy, qf;
    int pm, pi, sm, si;//前缀最大、最小，后缀最大、最小 
} t[MAXN];
int new_node(int x) {
    t[++cnt].siz = 1;
    t[cnt].ls = t[cnt].rs = t[cnt].lzy = t[cnt].qf = 0;
    t[cnt].fz = 0;
    t[cnt].key = t[cnt].sum = x;
    t[cnt].pri = rand();
    t[cnt].pm = t[cnt].pi = t[cnt].sm = t[cnt].si = 0;
    if (x == 1) t[cnt].pm = t[cnt].sm = 1;
    else t[cnt].pi = t[cnt].si = -1;
    return cnt;
} 
void pushup(int u) {
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
    t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + t[u].key;
    t[u].pm = max(t[t[u].ls].pm, t[t[u].ls].sum + t[u].key + t[t[u].rs].pm);
    t[u].pi = min(t[t[u].ls].pi, t[t[u].ls].sum + t[u].key + t[t[u].rs].pi);
    t[u].sm = max(t[t[u].rs].sm, t[t[u].rs].sum + t[u].key + t[t[u].ls].sm);
    t[u].si = min(t[t[u].rs].si, t[t[u].rs].sum + t[u].key + t[t[u].ls].si);
}
void reverse(int u) {
    if (u == 0) return;
    swap(t[u].ls, t[u].rs);
    swap(t[u].pm, t[u].sm);
    swap(t[u].pi, t[u].si);
    t[u].lzy ^= 1;
}
void cover(int u, int s) {
    if (u == 0) return;
    t[u].key = t[u].fz = s;
    t[u].sum = t[u].siz * s;
    // t[u].lzy = t[u].qf = 0;
    if (s == 1) {
        t[u].pm = t[u].sm = t[u].sum;
        t[u].pi = t[u].si = 0;
    } else {
        t[u].pm = t[u].sm = 0;
        t[u].pi = t[u].si = t[u].sum;
    }
}
void qwq(int u) {
    if (u == 0) return;
    t[u].sum *= -1, t[u].key *= -1;
    t[u].qf ^= 1;
    t[u].fz *= -1;
    int x = t[u].pm, y = t[u].pi;
    t[u].pm = -y, t[u].pi = -x;
    x = t[u].sm, y = t[u].si;
    t[u].sm = -y, t[u].si = -x;
}
void pushdown(int u) {
    if (u == 0) return;
    if (t[u].qf) {
        if (t[u].ls) qwq(t[u].ls);
        if (t[u].rs) qwq(t[u].rs);
        t[u].qf = 0;
    }
    if (t[u].fz) {
        if (t[u].ls) cover(t[u].ls, t[u].fz);
        if (t[u].rs) cover(t[u].rs, t[u].fz);
        t[u].fz = 0;
    }
    if (t[u].lzy) {
        if (t[u].ls) reverse(t[u].ls);
        if (t[u].rs) reverse(t[u].rs);
        t[u].lzy = 0;
    }
}
void split(int u, int x, int &l, int &r) {
    if (u == 0) {
        l = r = 0;
        return;
    }
    pushdown(u);
    if (t[t[u].ls].siz + 1 <= x) {
        l = u;
        split(t[u].rs, x - t[t[u].ls].siz - 1, t[u].rs, r);
    } else {
        r = u;
        split(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    if (t[l].pri > t[r].pri) {
        pushdown(l);
        t[l].rs = merge(t[l].rs, r);
        pushup(l);
        return l;
    } else {
        pushdown(r);
        t[r].ls = merge(l, t[r].ls);
        pushup(r);
        return r;
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    srand(time(0));
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        root = merge(root, new_node((c == '(' ? -1 : 1)));
    }
    while (m--) {
        string op;
        int x, y;
        char c;
        cin >> op;
        if (op == "Replace") {
            cin >> x >> y >> c;
            int l, r, p;
            split(root, x - 1, l, r);
            split(r, y - x + 1, r, p);
            cover(r, (c == '(' ? -1 : 1));
            root = merge(merge(l, r), p);
        } else if (op == "Swap") {
            cin >> x >> y;
            int l, r, p;
            split(root, x - 1, l, r);
            split(r, y - x + 1, r, p);
            reverse(r);
            root = merge(merge(l, r), p);
        } else if (op == "Invert") {
            cin >> x >> y;
            int l, r, p;
            split(root, x - 1, l, r);
            split(r, y - x + 1, r, p);
            qwq(r);
            root = merge(merge(l, r), p);
        } else {
            cin >> x >> y;
            int l, r, p;
            split(root, x - 1, l, r);
            split(r, y - x + 1, r, p);
            cout << ((t[r].pm + 1) / 2) + ((abs(t[r].si) + 1) / 2) << '\n';
            root = merge(merge(l, r), p);
        }
    }
    return 0;
}

::::

P5066 [Ynoi Easy Round 2014] 人人本着正义之名

你需要帮珂朵莉维护一个长为 n 的 01 序列 a，有 m 个操作：

1 l r：把区间 [l,r] 的数变成 0。

2 l r：把区间 [l,r] 的数变成 1。

3 l r：[l,r-1] 内所有数 a_i，变为 a_i 与 a_{i+1} 按位或的值，这些数同时进行这个操作。

4 l r：[l+1,r] 内所有数 a_i，变为 a_i 与 a_{i-1} 按位或的值，这些数同时进行这个操作。

5 l r：[l,r-1] 内所有数 a_i，变为 a_i 与 a_{i+1} 按位与的值，这些数同时进行这个操作。

6 l r：[l+1,r] 内所有数 a_i，变为 a_i 与 a_{i-1} 按位与的值，这些数同时进行这个操作。

7 l r：查询区间 [l,r] 的和。

~~无耻的复制自己的题解~~

发现这个 3, 4, 5, 6 操作有点特殊，考虑模拟一下：

0, 0, 0, 1, 1, 1, 0, 0, 1

对于整个序列进行 3 操作后：

0, 0, 1, 1, 1, 1, 0, 1, 1

发现，对于全是 0 的极长连续段，右端点向左收缩了一位，全是 1 的极长连续段，左端点向左扩展了一位。

同理，手玩这下操作，发现都是极长连续段进行扩展/收缩，那么对于这些量，可以打标记处理。

但是直接上 ODT 由于数据不随机会被卡，于是考虑使用平衡树维护 ODT，每个节点对应一个极长连续段，我使用的是 FHQ Treap。

除了常规平衡树维护的东西，我们需要维护区间对应的编号、区间中 1 的个数、0/1 极长连续段个数、最小 0/1 极长连续段，以及扩展/收缩对应的标记。

接下来讲解代码。

新建节点

没什么好说的。

::::success[code]

//[l, r] 全部为 v 的极长连续段
struct node {
    int ls, rs;
    int pri, siz;
    int key;
    int l, r;//区间编号 
    int sum, cnt[2];//1 的个数，子树中 0/1 段个数 
    int Min[2];//子树中最小 0/1 段 
    int ltag[2], rtag[2];//0/1 段左右移动量 
} t[MAXN];
void new_node(int &p, int l, int r, int v) {
    p = ++cnt;
    t[p].ls = t[p].rs = 0;
    t[p].siz = 1;
    t[p].ltag[0] = t[p].ltag[1] = t[p].rtag[0] = t[p].rtag[1] = 0;
    t[p].key = v;
    t[p].pri = rand();
    t[p].l = l;
    t[p].r = r;
    t[p].sum = (r - l + 1) * v;
    t[p].cnt[v] = 1;
    t[p].cnt[v ^ 1] = 0;
    t[p].Min[v] = r - l + 1;
    t[p].Min[v ^ 1] = inf;
}

::::

pushup

还是没什么好说的，注意不是这个区间颜色的 Min 以及 cnt，直接取左右子树最小值/相加即可。

::::success[code]

void pushup(int u) {
    if (!u) return;
    t[u].siz = t[t[u].ls].siz + t[t[u].rs].siz + 1;
    t[u].sum = t[t[u].ls].sum + t[t[u].rs].sum + (t[u].r - t[u].l + 1) * t[u].key;
    t[u].cnt[t[u].key] = t[t[u].ls].cnt[t[u].key] + t[t[u].rs].cnt[t[u].key] + 1;
    t[u].cnt[t[u].key ^ 1] = t[t[u].ls].cnt[t[u].key ^ 1] + t[t[u].rs].cnt[t[u].key ^ 1];
    t[u].Min[t[u].key] = min(min(t[t[u].ls].Min[t[u].key], t[t[u].rs].Min[t[u].key]), t[u].r - t[u].l + 1);
    t[u].Min[t[u].key ^ 1] = min(t[t[u].ls].Min[t[u].key ^ 1], t[t[u].rs].Min[t[u].key ^ 1]);
}

::::

maketag & pushdown

其实也没什么好说的，只是对于 Min_{0/1} 和 sum，需要增加对应偏移量。

::::success[code]

void maketag(int u, int lt0, int lt1, int rt0, int rt1) {//左右移动量 
    if (!u) return;
    t[u].Min[0] += rt0 - lt0;
    t[u].Min[1] += rt1 - lt1;
    t[u].ltag[0] += lt0, t[u].ltag[1] += lt1;
    t[u].rtag[0] += rt0, t[u].rtag[1] += rt1;
    t[u].sum += t[u].cnt[1] * (rt1 - lt1);
    if (t[u].key) t[u].l += lt1, t[u].r += rt1;
    else t[u].l += lt0, t[u].r += rt0;
}
void pushdown(int u) {
    if (!u) return;
    if (t[u].ltag[0] || t[u].ltag[1] || t[u].rtag[0] || t[u].rtag[1]) {
        maketag(t[u].ls, t[u].ltag[0], t[u].ltag[1], t[u].rtag[0], t[u].rtag[1]);
        maketag(t[u].rs, t[u].ltag[0], t[u].ltag[1], t[u].rtag[0], t[u].rtag[1]);
        t[u].ltag[0] = t[u].ltag[1] = t[u].rtag[0] = t[u].rtag[1] = 0;
    }
}

::::

分裂与合并

由于维护的是连续段，所以不能向通常 FHQ Treap 一样分裂，而需要按左右端点分裂分出一个区间。

::::success[code]

//按左端点分裂 
void splitl(int u, int x, int &l, int &r) {
    if (u == 0) { l = r = 0; return; }
    pushdown(u);
    if (t[u].l <= x) {
        l = u;
        splitl(t[u].rs, x, t[u].rs, r);
    } else {
        r = u;
        splitl(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
//按右端点分裂 
void splitr(int u, int x, int &l, int &r) {
    if (u == 0) { l = r = 0; return; }
    pushdown(u);
    if (t[u].r < x) {
        l = u;
        splitr(t[u].rs, x, t[u].rs, r);
    } else {
        r = u;
        splitr(t[u].ls, x, l, t[u].ls);
    }
    pushup(u);
}
int merge(int l, int r) {
    if (l == 0 || r == 0) return l + r;
    if (t[l].pri < t[r].pri) {
        pushdown(l);
        t[l].rs = merge(t[l].rs, r);
        pushup(l);
        return l;
    } else {
        pushdown(r);
        t[r].ls = merge(l, t[r].ls);
        pushup(r);
        return r;
    }
}

::::

区间赋值

首先分出 [l, r] 对应区间，设 L, R 为区间中最左/最右连续段。

处理左边界：
- 若 L 对应颜色与修改的 val 相同，则修改区间和 L 可以合并成一个极长连续段。
- 否则，L 左端点到 l - 1 单独一个极长连续段。
处理右边界，与左边界同理：
- 若 R 对应颜色与修改的 val 相同，则修改区间和 R 可以合并成一个极长连续段。
- 否则，r + 1 到 R 右端点单独一个极长连续段。
若分裂出的左半区间的最右区间，与 [l, r] 同色，则和修改区间合并成一个极长连续段，并删除这一段区间。
若分裂出的右半区间的最左区间，与 [l, r] 同色，则和修改区间合并成一个极长连续段，并删除这一段区间。

::::success[code]

//Left 和 Right 是找到子树种最左/右连续段
void assign(int l, int r, int v) {
    int x, y, p;
    splitr(root, l, x, y);
    splitl(y, r, y, p);
    int L = Left(y), R = Right(y);
    // 处理左边界
    if (t[L].key == v) l = t[L].l;
    else {
        int tmp;
        new_node(tmp, t[L].l, l - 1, t[L].key);
        x = merge(x, tmp);
    }
    // 处理右边界
    if (t[R].key == v) r = t[R].r;
    else {
        int tmp;
        new_node(tmp, r + 1, t[R].r, t[R].key);
        p = merge(tmp, p);
    }
    // 检查 x 的右边界是否与新区间同色
    if (x) {
        L = Right(x);
        if (t[L].key == v) {
            l = t[L].l;
            splitr(x, t[L].l, x, L);
        }
    }
    // 检查 p 的左边界是否与新区间同色
    if (p) {
        R = Left(p);
        if (t[R].key == v) {
            r = t[R].r;
            splitr(p, t[R].r + 1, R, p);
        }
    }
    int tmp;
    new_node(tmp, l, r, v);
    root = merge(merge(x, tmp), p);
}

::::

扩展/收缩区间

首先分出 [l, r] 对应区间，设 L, R 为区间中最左/最右连续段。

若 L 颜色与对应颜色相同，则分裂出去，合并到左半区间。
若 R 颜色与对应颜色不同，则分裂出去，合并到右半区间。

最后 maketag。

::::success[code]

void update(int l, int r, int col, int lt0, int lt1, int rt0, int rt1) {
    int x, yp, p;
    splitr(root, l, x, yp);
    splitl(yp, r, yp, p);
    if (!yp) {
        root = merge(x, p);
        return;
    }
    int L = Left(yp), R = Right(yp);
    //切出去归 x 
    if (t[L].key == col) {
        splitl(yp, t[L].l, L, yp);
        x = merge(x, L);
        if (!yp) {
            root = merge(x, p);
            return;
        }
        L = Left(yp);
    }
    //扩出去归 p 
    if (t[R].key != col) {
        splitr(yp, t[R].l, yp, R);
        p = merge(R, p);
        if (!yp) {
            root = merge(x, p);
            return;
        }
        R = Right(yp);
    }
    maketag(yp, lt0, lt1, rt0, rt1);
    root = merge(merge(x, yp), p);
}

::::

查询

分裂出来的和减去最左/右多出的即可。

::::success[code]

int query(int l, int r) {
    int x, y, p;
    splitr(root, l, x, y);
    splitl(y, r, y, p);
    int L = Left(y), R = Right(y);
    //减去左右边多出的 
    int res = t[y].sum - (l - t[L].l) * t[L].key - (t[R].r - r) * t[R].key;
    root = merge(merge(x, y), p);
    return res;
}

::::

处理空段

处理每次操作完后平衡树中的空段。

如果当前段是空段（l > r）：
- 如果是序列中最左边的段或者最右边，直接分裂出去。
- 否则，设 L, R 为当前区间最左/右极长连续段，将 [L, R] 重新作为一个极长连续段。
否则继续递归。

::::success[code]

void clear(int u) {
    if (!u) return;
    pushdown(u);
    //删除空段 
    if (t[u].l > t[u].r) {
        int x, y, p;
        if (t[u].l == 1) {
            splitr(root, 1, x, root);
            return;
        }
        if (t[u].r == n) {
            splitl(root, n, root, x);
            return;
        }
        splitr(root, t[u].r, x, y);
        splitl(y, t[u].l, y, p);
        int L = Left(y), R = Right(y);
        new_node(y, t[L].l, t[R].r, t[L].key);
        root = merge(merge(x, y), p);
        return;
    }
    //可能是空段，继续递归
    if (min(t[t[u].ls].Min[0], t[t[u].ls].Min[1]) <= 0) {
        clear(t[u].ls);
        return;
    }
    if (min(t[t[u].rs].Min[0], t[t[u].rs].Min[1]) <= 0) clear(t[u].rs);
}

::::

主函数

建树之后处理操作即可。

::::success[code]

cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
//建树 
int idx = 1;
while (idx <= n) {
    int r = idx;
    while (r < n && a[idx] == a[r + 1]) r++;
    int tmp;
    new_node(tmp, idx, r, a[idx]);
    root = merge(root, tmp);
    idx = r + 1;
}
int last = 0;
while (m--) {
    int op, l, r;
    cin >> op >> l >> r;
    l ^= last, r ^= last;
    //处理操作 
    if (op == 1) {
        assign(l, r, 0);
    } else if (op == 2) {
        assign(l, r, 1);
    } else if (op == 3) {
        update(l, r, 1, 0, -1, -1, 0);
    } else if (op == 4) {
        update(l, r, 0, 1, 0, 0, 1);
    } else if (op == 5) {
        update(l, r, 0, -1, 0, 0, -1);
    } else if (op == 6) {
        update(l, r, 1, 0, 1, 1, 0);
    } else if (op == 7) {
        last = query(l, r);
        cout << last << '\n';
    }
    //清除空段 
    while (min(t[root].Min[0], t[root].Min[1]) <= 0) clear(root);
}

::::

本文章使用了 deepseek-v4-pro 进行润色以保证格式的正确。