2025 暑 TYOI 集训小记

/*
* @file std-datastruct.cpp
* @author Federico Prask
* @time 2025-08-08
* 本文件实现了多种常见的数据结构，包括线段树、Treap、FHQ-Treap等
*/

// 包含标准库头文件
#include <bits/stdc++.h>

// 定义文件输入输出宏，方便处理文件IO
// #s会将参数转换为字符串，用于生成文件名
#define file(s) \
    std::freopen(#s".in", "r", stdin), std::freopen(#s".out", "w", stdout)

// 定义类型别名
using i64 = long long;        // 64位有符号整数
using ull = unsigned long long; // 64位无符号整数
using f32 = double;           // 32位浮点数
using ldb = long double;      // 扩展精度浮点数

// 命名空间trix，包含快速输入函数
namespace trix{
    // 读取整数
    inline int readint() {
        register int x = 0, sign = 1;  // x存储结果，sign存储符号
        register char ch = getchar();  // 读取第一个字符
        // 跳过非数字字符
        for (; !isdigit(ch); ch = getchar()) {
            if (ch == '-') {    // 处理负号
                sign = -1;
            }
            if (ch == EOF) {     // 处理文件结束
                return EOF;
            }
        }
        // 处理数字部分
        for (; isdigit(ch); ch = getchar()) {
            x = x * 10 + ch - '0';  // 逐位构建整数
        }
        return x * sign;  // 返回带符号的结果
    }

    // 读取64位整数（实现与readint类似）
    inline i64 readi64() {
        register i64 x = 0, sign = 1;
        register char ch = getchar();
        for (; !isdigit(ch); ch = getchar()) {
            if (ch == '-') {    
                sign = -1;
            }
            if (ch == EOF) {
                return EOF;
            }
        }
        for (; isdigit(ch); ch = getchar()) {
            x = x * 10 + ch - '0';
        }
        return x * sign;
    }

    // 读取字符（跳过空格和换行）
    inline char readchar() {
        register char ch = getchar();
        for (; ch == ' ' || ch == '\n'; ch = getchar()) {
            continue;  // 跳过空白字符
        }
        return ch;  // 返回第一个非空白字符
    }
}

// 数据结构命名空间
namespace DataStruct {
    template<int MAXN, int MAXK>
    class MoAlgorithm {
        // 查询结构体
        struct Query {
            int l, r, id;  // 查询区间[l,r]和查询id

            // 排序比较函数（奇偶块优化）
            bool operator<(const Query &q) const {
                if (l / BLOCK_SIZE != q.l / BLOCK_SIZE)
                    return l < q.l;
                return (l / BLOCK_SIZE & 1) ? r < q.r : r > q.r;
            }
        };

        int n, m, k;               // 元素数量、查询数量、特定值k
        int BLOCK_SIZE;            // 分块大小
        i64 nowAns;                // 当前答案
        int a[MAXN], prefix[MAXN]; // 原数组和前缀异或数组
        i64 ans[MAXN];             // 存储每个查询的答案
        int cnt[MAXK];             // 计数数组
        Query querys[MAXN];        // 查询数组

    public:
        // 构造函数
        MoAlgorithm() : nowAns(0) {
            std::memset(cnt, 0, sizeof(cnt));
        }

        // 设置分块大小（可选）
        void setBlockSize(int size) {
            BLOCK_SIZE = size;
        }

        // 初始化数据
        void init(int _n, int _m, int _k) {
            n = _n;
            m = _m;
            k = _k;

            // 如果没有设置分块大小，使用默认计算
            if (BLOCK_SIZE == 0) {
                BLOCK_SIZE = std::max(1, (int)(n / sqrt(m)));
            }
        }

        // 添加元素到数组
        void addElement(int pos, int val) {
            a[pos] = val;
        }

        // 添加查询
        void addQuery(int id, int l, int r) {
            querys[id] = {l, r, id};
        }

        // 计算前缀异或数组
        void computePrefix() {
            prefix[0] = 0;
            for (int i = 1; i <= n; ++i) {
                prefix[i] = prefix[i - 1] ^ a[i];
            }
        }

        // 运行莫队算法
        void run() {
            std::sort(querys, querys + m);

            int l = 1, r = 0;
            nowAns = 0;
            cnt[0] = 1;  // 初始化前缀和0出现1次

            for (int i = 0; i < m; ++i) {
                const Query &q = querys[i];

                // 扩展左边界
                while (l > q.l) {
                    l--;
                    add(l - 1);  // 注意这里是l-1，因为计算的是前缀和
                }
                // 扩展右边界
                while (r < q.r) {
                    r++;
                    add(r);
                }
                // 收缩左边界
                while (l < q.l) {
                    remove(l - 1);
                    l++;
                }
                // 收缩右边界
                while (r > q.r) {
                    remove(r);
                    r--;
                }

                ans[q.id] = nowAns;
            }
        }

        // 获取查询结果
        i64 getAnswer(int id) const {
            return ans[id];
        }

        // 打印所有查询结果
        void printAnswers() const {
            for (int i = 0; i < m; ++i) {
                printf("%lld\n", ans[i]);
            }
        }

    private:
        // 添加位置到当前区间
        inline void add(int pos) {
            nowAns += cnt[prefix[pos] ^ k];
            cnt[prefix[pos]]++;
        }

        // 从当前区间移除位置
        inline void remove(int pos) {
            cnt[prefix[pos]]--;
            nowAns -= cnt[prefix[pos] ^ k];
        }
    };
    // 线段树模板类（区间加法）
    // _N是最大节点数
    template<int _N>
    class Segment_Tree_Segadd {
        // 线段树节点结构
        struct binary_tree {
            i64 left_son = 0, right_son = 0;  // 区间左右端点
            i64 value = 0, addition = 0;     // 区间值和懒惰标记
        } node[_N << 2];  // 4倍空间
        i64 *a;  // 指向外部数组的指针

        public:
            // 构建线段树
            void build_tree(i64 n, i64 *_a) {
                a = _a;  // 保存外部数组指针
                _build_tree(1, 1, n);  // 从根节点开始构建
            }

            // 区间更新
            void update(i64 l, i64 r, i64 val) {
                if (l > r) return;  // 无效区间直接返回
                _update(1, l, r, val);  // 从根节点开始更新
            }

            // 区间查询
            i64 query(i64 l, i64 r) {
                if (l > r) return 0;  // 无效区间返回0
                return _query(1, l, r);  // 从根节点开始查询
            }

        private:
            // 上推更新，合并子节点信息
            void pushup(i64 x) {
                node[x].value = node[x << 1].value + node[(x << 1) | 1].value;
            }

            // 下推懒惰标记
            void pushdown(i64 x) {
                if (node[x].addition) {  // 如果有懒惰标记
                    i64 left = x << 1;   // 左子节点
                    i64 right = (x << 1) | 1;  // 右子节点
                    i64 len_left = node[left].right_son - node[left].left_son + 1;  // 左区间长度
                    i64 len_right = node[right].right_son - node[right].left_son + 1;  // 右区间长度

                    // 更新子节点的懒惰标记和值
                    node[left].addition += node[x].addition;
                    node[right].addition += node[x].addition;
                    node[left].value += node[x].addition * len_left;
                    node[right].value += node[x].addition * len_right;
                    node[x].addition = 0;  // 清空当前节点的懒惰标记
                }
            }

            // 递归构建线段树
            void _build_tree(i64 x, i64 l, i64 r) {
                node[x].left_son = l;
                node[x].right_son = r;
                node[x].addition = 0;  // 初始化懒惰标记
                if (l == r) {  // 叶子节点
                    node[x].value = a[l];  // 直接赋值
                    return;
                }
                i64 mid = (l + r) >> 1;  // 计算中点
                _build_tree(x << 1, l, mid);      // 构建左子树
                _build_tree((x << 1) | 1, mid + 1, r);  // 构建右子树
                pushup(x);  // 合并子节点信息
            }

            // 递归更新区间
            void _update(i64 now, i64 l, i64 r, i64 k) {
                // 当前区间完全包含在更新区间内
                if (l <= node[now].left_son && r >= node[now].right_son) {
                    // 更新区间值和懒惰标记
                    node[now].value += k * (node[now].right_son - node[now].left_son + 1);
                    node[now].addition += k;
                    return;
                }

                pushdown(now);  // 下推懒惰标记
                i64 mid = (node[now].left_son + node[now].right_son) >> 1;
                if (l <= mid) _update(now << 1, l, r, k);      // 更新左子树
                if (r > mid) _update((now << 1) | 1, l, r, k);  // 更新右子树
                pushup(now);  // 合并子节点信息
            }

            // 递归查询区间
            i64 _query(i64 x, i64 l, i64 r) {
                // 当前区间完全包含在查询区间内
                if (l <= node[x].left_son && node[x].right_son <= r) {
                    return node[x].value;  // 直接返回值
                }
                pushdown(x);  // 下推懒惰标记
                i64 mid = (node[x].left_son + node[x].right_son) >> 1;
                i64 sum = 0;
                if (l <= mid) {
                    sum += _query(x << 1, l, r);  // 查询左子树
                }
                if (r > mid) {
                    sum += _query((x << 1) | 1, l, r);  // 查询右子树
                }
                return sum;
            }
        };

    // 线段树模板类（区间覆盖）
    // 实现与Segment_Tree_Segadd类似，主要区别在于覆盖操作
    template<int _N>
    class Segment_Tree_Segcover {
        struct binary_tree {
            i64 left_son = 0, right_son = 0;
            i64 value = 0, cover = 0;  // cover存储覆盖值
            bool has_cover = false;     // 标记是否被覆盖
        } node[_N << 2];
        i64 *a;

        public:
            void build_tree(i64 n, i64 *_a) {
                a = _a;
                _build_tree(1, 1, n);
            }
            void update(i64 l, i64 r, i64 val) {
                if (l > r) return;
                _update(1, l, r, val);
            }
            i64 query(i64 l, i64 r) {
                if (l > r) return 0;
                return _query(1, l, r);
            }

        private:
            void pushup(i64 x) {
                node[x].value = node[x << 1].value + node[(x << 1) | 1].value;
            }
            void pushdown(i64 x) {
                if (node[x].has_cover) {  // 如果有覆盖标记
                    i64 left = x << 1;
                    i64 right = (x << 1) | 1;
                    i64 len_left = node[left].right_son - node[left].left_son + 1;
                    i64 len_right = node[right].right_son - node[right].left_son + 1;

                    // 覆盖子节点
                    node[left].cover = node[x].cover;
                    node[right].cover = node[x].cover;
                    node[left].value = node[x].cover * len_left;
                    node[right].value = node[x].cover * len_right;
                    node[left].has_cover = true;
                    node[right].has_cover = true;

                    node[x].has_cover = false;  // 清除覆盖标记
                }
            }
            void _build_tree(i64 x, i64 l, i64 r) {
                node[x].left_son = l;
                node[x].right_son = r;
                node[x].has_cover = false;
                if (l == r) {
                    node[x].value = a[l];
                    return;
                }
                i64 mid = (l + r) >> 1;
                _build_tree(x << 1, l, mid);
                _build_tree((x << 1) | 1, mid + 1, r);
                pushup(x);
            }
            void _update(i64 now, i64 l, i64 r, i64 k) {
                if (l <= node[now].left_son && r >= node[now].right_son) {
                    // 覆盖操作
                    node[now].value = k * (node[now].right_son - node[now].left_son + 1);
                    node[now].cover = k;
                    node[now].has_cover = true;
                    return;
                }

                pushdown(now);
                i64 mid = (node[now].left_son + node[now].right_son) >> 1;
                if (l <= mid) _update(now << 1, l, r, k);
                if (r > mid) _update((now << 1) | 1, l, r, k);
                pushup(now);
            }
            i64 _query(i64 x, i64 l, i64 r) {
                if (l <= node[x].left_son && node[x].right_son <= r) {
                    return node[x].value;
                }
                pushdown(x);
                i64 mid = (node[x].left_son + node[x].right_son) >> 1;
                i64 sum = 0;
                if (l <= mid) {
                    sum += _query(x << 1, l, r);
                }
                if (r > mid) {
                    sum += _query((x << 1) | 1, l, r);
                }
                return sum;
            }
    };

    // Treap (树堆) - 一种平衡二叉搜索树
    class Treap {
        // 使用数组实现二叉树
        static const int MN = 2100005;  // 最大节点数
        int l[MN], r[MN];      // 左右子节点索引
        int value[MN];         // 节点值
        int rand_val[MN];      // 随机优先级
        int sz[MN];           // 子树大小
        int w[MN];            // 相同值的计数
        int nans, size;       // 临时答案和当前大小
        int root;            // 根节点索引

        public:
            Treap() : root(0), size(0), nans(0) {
                std::memset(l, 0, sizeof(l));
                std::memset(r, 0, sizeof(r));
                std::srand(std::time(0));  // 初始化随机数种子
            }

            // 查询值的排名
            int qrnk(int x) {
                return queryrank(root, x);
            }

            // 查询排名对应的值
            int qnum(int x) {
                return querynum(root, x);
            }

            // 查询前驱
            int qpre(int x) {
                nans = 0;  // 重置临时答案
                querypre(root, x);
                return nans ? value[nans] : -2147483647;  // 返回前驱值或最小值
            }

            // 查询后继
            int qsub(int x) {
                nans = 0;
                querysub(root, x);
                return nans ? value[nans] : 2147483647;  // 返回后继值或最大值
            }

            // 删除值
            void del(int x) {
                _delete(root, x);
            }

            // 插入值
            void ins(int x) {
                _insert(root, x);
            }

        private:
            // 更新子树大小
            void pushup(int x) {
                sz[x] = sz[l[x]] + sz[r[x]] + w[x];
            }

            // 左旋
            void left_rotate(int &k) {
                int t = r[k];
                r[k] = l[t];
                l[t] = k;
                sz[t] = sz[k];  // 更新大小
                pushup(k);      // 重新计算k的大小
                k = t;          // k指向新的根
            }

            // 右旋
            void right_rotate(int &k) {
                int t = l[k];
                l[k] = r[t];
                r[t] = k;
                sz[t] = sz[k];
                pushup(k);
                k = t;
            }

            // 递归插入
            void _insert(int &k, int x) {
                if (!k) {  // 空节点，创建新节点
                    size++;
                    k = size;
                    sz[k] = 1;
                    w[k] = 1;
                    value[k] = x;
                    rand_val[k] = rand();  // 设置随机优先级
                    return;
                }
                sz[k]++;  // 增加当前节点大小
                if (value[k] == x) {  // 值已存在，增加计数
                    w[k]++;
                } else if (value[k] < x) {  // 插入右子树
                    _insert(r[k], x);
                    if (rand_val[r[k]] < rand_val[k]) {  // 维护堆性质
                        left_rotate(k);
                    }
                } else {  // 插入左子树
                    _insert(l[k], x);
                    if (rand_val[l[k]] < rand_val[k]) {  // 维护堆性质
                        right_rotate(k);
                    }
                }
            }

            // 递归删除
            bool _delete(int &k, int x) {
                if (!k) {  // 值不存在
                    return false;
                }
                if (value[k] == x) {  // 找到要删除的值
                    if (w[k] > 1) {   // 有多个相同值，只需减少计数
                        w[k]--;
                        sz[k]--;
                        return true;
                    }
                    if (l[k] == 0 || r[k] == 0) {  // 只有一个子节点或没有子节点
                        k = l[k] + r[k];  // 用子节点替代
                        return true;
                    } else if (rand_val[l[k]] < rand_val[r[k]]) {  // 根据优先级旋转
                        right_rotate(k);
                        return _delete(k, x);
                    } else {
                        left_rotate(k);
                        return _delete(k, x);
                    }
                } else if (value[k] < x) {  // 在右子树中删除
                    bool succ = _delete(r[k], x);
                    if (succ) {
                        sz[k]--;  // 更新大小
                    }
                    return succ;
                } else {  // 在左子树中删除
                    bool succ = _delete(l[k], x);
                    if (succ) {
                        sz[k]--;
                    }
                    return succ;
                }
            }

            // 查询值的排名
            int queryrank(int k, int x) {
                if (!k) {
                    return 1;  // 空树返回1
                }
                if (value[k] == x) {  // 找到值
                    return sz[l[k]] + 1;  // 左子树大小+1
                } else if (x > value[k]) {  // 在右子树中查询
                    return sz[l[k]] + w[k] + queryrank(r[k], x);
                } else {  // 在左子树中查询
                    return queryrank(l[k], x);
                }
            }

            // 查询排名对应的值
            int querynum(int k, int x) {
                if (!k) {
                    return 0;
                }
                if (x <= sz[l[k]]) {  // 在左子树中
                    return querynum(l[k], x);
                }
                else if (x > sz[l[k]] + w[k]) {  // 在右子树中
                    return querynum(r[k], x - sz[l[k]] - w[k]);
                }
                else {  // 当前节点
                    return value[k];
                }
            }

            // 查询前驱
            void querypre(int k, int x) {
                if (!k) {
                    return;
                }
                if (value[k] < x) {  // 当前节点可能是前驱
                    nans = k;       // 保存候选节点
                    querypre(r[k], x);  // 继续在右子树中寻找更大的前驱
                }
                else {
                    querypre(l[k], x);  // 在左子树中寻找
                }
            }

            // 查询后继
            void querysub(int k, int x) {
                if (!k) {
                    return;
                }
                if (value[k] > x) {  // 当前节点可能是后继
                    nans = k;        // 保存候选节点
                    querysub(l[k], x);  // 继续在左子树中寻找更小的后继
                }
                else {
                    querysub(r[k], x);  // 在右子树中寻找
                }
            }
    };

    // FHQ-Treap (非旋转Treap)
    class FHQTreap {
        static const int MN = 2100005;  // 最大节点数
        int l[MN], r[MN];      // 左右子节点
        int value[MN];         // 节点值
        int rand_val[MN];      // 随机优先级
        int sz[MN];           // 子树大小
        int cnt, root;        // 节点计数和根节点

        public:
            FHQTreap() : root(0), cnt(0) {
                std::memset(l, 0, sizeof(l));
                std::memset(r, 0, sizeof(r));
                std::srand(std::time(0));  // 初始化随机数种子
            }

            // 插入值
            void ins(int x) {
                int a, b;
                split(root, x, a, b);  // 按x分割
                root = merge(merge(a, new_node(x)), b);  // 合并
            }

            // 删除值
            void del(int x) {
                int a, b, c;
                split(root, x, a, b);       // 按x分割
                split(b, x + 1, b, c);      // 按x+1分割，分离出x
                if (b) {
                    b = merge(l[b], r[b]);   // 合并b的左右子树（相当于删除b）
                }
                root = merge(merge(a, b), c);  // 重新合并
            }

            // 查询排名
            int qrnk(int x) {
                int a, b;
                split(root, x - 1, a, b);   // 按x-1分割
                int res = sz[a] + 1;        // a的大小+1就是x的排名
                root = merge(a, b);         // 恢复树
                return res;
            }

            // 查询排名对应的值
            int qnum(int k) {
                return kth(root, k);  // 查找第k小
            }

            // 查询前驱
            int qpre(int x) {
                int a, b;
                split(root, x - 1, a, b);   // 按x-1分割
                int res = kth(a, sz[a]);   // a中最大的就是前驱
                root = merge(a, b);
                return res;
            }

            // 查询后继
            int qsub(int x) {
                int a, b;
                split(root, x, a, b);      // 按x分割
                int res = kth(b, 1);        // b中最小的就是后继
                root = merge(a, b);
                return res;
            }

        private:
            // 创建新节点
            int new_node(int x) {
                cnt++;
                value[cnt] = x;
                rand_val[cnt] = rand();  // 随机优先级
                sz[cnt] = 1;            // 初始大小
                return cnt;
            }

            // 更新子树大小
            void pushup(int x) {
                sz[x] = sz[l[x]] + sz[r[x]] + 1;
            }

            // 按值分割树
            void split(int now, int k, int &x, int &y) {
                if (!now) {  // 空树
                    x = y = 0;
                    return;
                }
                if (value[now] <= k) {  // 当前节点值<=k，归入x树
                    x = now;
                    split(r[now], k, r[now], y);  // 继续分割右子树
                } else {  // 当前节点值>k，归入y树
                    y = now;
                    split(l[now], k, x, l[now]);  // 继续分割左子树
                }
                pushup(now);  // 更新大小
            }

            // 合并两棵树
            int merge(int x, int y) {
                if (!x || !y) {  // 任意一棵树为空，返回另一棵
                    return x | y;
                }
                // 按优先级合并
                if (rand_val[x] < rand_val[y]) {  // x的优先级更高
                    r[x] = merge(r[x], y);       // y合并到x的右子树
                    pushup(x);
                    return x;
                } else {  // y的优先级更高
                    l[y] = merge(x, l[y]);       // x合并到y的左子树
                    pushup(y);
                    return y;
                }
            }

            // 查找第k小的值
            int kth(int now, int k) {
                while (true) {
                    if (k <= sz[l[now]]) {  // 在左子树中
                        now = l[now];
                    } else if (k == sz[l[now]] + 1) {  // 当前节点
                        return value[now];
                    } else {  // 在右子树中
                        k -= sz[l[now]] + 1;
                        now = r[now];
                    }
                }
            }
    };

    // 可持久化FHQ-Treap
    class PersistentFHQTreap {
        static const int MN = 5e5 + 10;  // 最大节点数
        static const int INF = 2147483647;  // 无穷大

        // 节点结构
        struct Node {
            int l, r;      // 左右子节点
            int val, key;  // 值和随机优先级
            int size;      // 子树大小
        } t[MN * 50];     // 可持久化需要更多空间

        public:
            int root[MN], cnt;  // 多个版本的根和节点计数
            PersistentFHQTreap() : cnt(0) {
                std::fill(root, root + MN, 0);
                std::srand(std::time(0));  // 初始化随机数种子
            }

            // 插入值（创建新版本）
            void insert(int ver, int new_ver, int val) {
                root[new_ver] = root[ver];  // 基于旧版本
                int x, y;
                split(root[new_ver], val, x, y);  // 分割
                root[new_ver] = merge(merge(x, new_node(val)), y);  // 合并
            }

            // 删除值（创建新版本）
            void remove(int ver, int new_ver, int val) {
                root[new_ver] = root[ver];  // 基于旧版本
                int x, y, z;
                split(root[new_ver], val, x, z);      // 按val分割
                split(x, val - 1, x, y);               // 按val-1分割
                if (y) y = merge(t[y].l, t[y].r);      // 合并y的左右子树（相当于删除y）
                root[new_ver] = merge(merge(x, y), z);  // 重新合并
            }

            // 查询排名
            int get_rank(int ver, int val) {
                int x, y;
                split(root[ver], val - 1, x, y);  // 按val-1分割
                int res = t[x].size + 1;         // x的大小+1就是排名
                root[ver] = merge(x, y);         // 恢复
                return res;
            }

            // 查询排名对应的值
            int get_val(int ver, int rank) {
                return _get_val(root[ver], rank);
            }

            // 查询前驱
            int get_prev(int ver, int val) {
                int x, y;
                split(root[ver], val - 1, x, y);  // 按val-1分割
                if (!x) return -INF + 1;         // 没有前驱
                int res = _get_val(x, t[x].size); // x中最大的就是前驱
                root[ver] = merge(x, y);
                return res;
            }

            // 查询后继
            int get_next(int ver, int val) {
                int x, y;
                split(root[ver], val, x, y);  // 按val分割
                if (!y) return INF;           // 没有后继
                int res = _get_val(y, 1);     // y中最小的就是后继
                root[ver] = merge(x, y);
                return res;
            }

        private:
            // 创建新节点
            int new_node(int val) {
                t[++cnt] = {0, 0, val, rand(), 1};  // 初始化新节点
                return cnt;
            }

            // 克隆节点（用于可持久化）
            int clone(int p) {
                if (!p) return 0;
                t[++cnt] = t[p];  // 复制节点
                return cnt;
            }

            // 更新子树大小
            void pushup(int p) {
                t[p].size = t[t[p].l].size + t[t[p].r].size + 1;
            }

            // 按值分割树（可持久化版本）
            void split(int p, int val, int &x, int &y) {
                if (!p) {
                    x = y = 0;
                    return;
                }
                p = clone(p);  // 克隆节点
                if (t[p].val <= val) {  // 当前节点值<=val，归入x树
                    x = p;
                    split(t[x].r, val, t[x].r, y);  // 继续分割右子树
                } else {  // 当前节点值>val，归入y树
                    y = p;
                    split(t[y].l, val, x, t[y].l);  // 继续分割左子树
                }
                pushup(p);  // 更新大小
            }

            // 合并两棵树（可持久化版本）
            int merge(int x, int y) {
                if (!x || !y) return x | y;
                if (t[x].key < t[y].key) {  // x优先级更高
                    x = clone(x);           // 克隆x
                    t[x].r = merge(t[x].r, y);  // y合并到x的右子树
                    pushup(x);
                    return x;
                } else {  // y优先级更高
                    y = clone(y);           // 克隆y
                    t[y].l = merge(x, t[y].l);  // x合并到y的左子树
                    pushup(y);
                    return y;
                }
            }

            // 查找第k小的值
            int _get_val(int p, int rank) {
                while (true) {
                    if (rank <= t[t[p].l].size) {  // 在左子树中
                        p = t[p].l;
                    } else if (rank == t[t[p].l].size + 1) {  // 当前节点
                        return t[p].val;
                    } else {  // 在右子树中
                        rank -= t[t[p].l].size + 1;
                        p = t[p].r;
                    }
                }
            }
    };

    // 可持久化文艺平衡树
    class PersistentWenYiTreap {
        static const int MN = 5e5 + 10;  // 最大节点数
        static const int INF = 2147483647;  // 无穷大

        // 节点结构
        struct Node {
            int l, r;        // 左右子节点
            int val, key;    // 值和随机优先级
            int size;        // 子树大小
            long long sum;   // 子树和（文艺平衡树新增）
            bool rev;        // 翻转标记（文艺平衡树新增）
        } t[MN * 50];       // 可持久化需要更多空间

        public:
            int root[MN], cnt;  // 多个版本的根和节点计数
            PersistentWenYiTreap() : cnt(0) {
                std::fill(root, root + MN, 0);
                std::srand(std::time(0));  // 初始化随机数种子
            }

            // 在位置pos后插入值val（创建新版本）
            void insert(int ver, int new_ver, int pos, int val) {
                root[new_ver] = root[ver];  // 基于旧版本
                int x, y;
                split_by_rank(root[new_ver], pos, x, y);  // 按位置分割
                root[new_ver] = merge(merge(x, new_node(val)), y);  // 合并
            }

            // 删除位置pos的值（创建新版本）
            void remove(int ver, int new_ver, int pos) {
                root[new_ver] = root[ver];  // 基于旧版本
                int x, y, z;
                split_by_rank(root[new_ver], pos, x, z);      // 按pos分割
                split_by_rank(x, pos - 1, x, y);               // 按pos-1分割
                root[new_ver] = merge(x, z);                   // 跳过y（相当于删除）
            }

            // 区间翻转（创建新版本）
            void reverse(int ver, int new_ver, int l, int r) {
                root[new_ver] = root[ver];  // 基于旧版本
                int x, y, z;
                split_by_rank(root[new_ver], r, y, z);     // 先分割出前r个
                split_by_rank(y, l - 1, x, y);             // 再分割出l到r
                t[y].rev ^= 1;                            // 打上翻转标记
                root[new_ver] = merge(merge(x, y), z);     // 重新合并
            }

            // 查询区间和
            long long query_sum(int ver, int l, int r) {
                int x, y, z;
                split_by_rank(root[ver], r, y, z);        // 先分割出前r个
                split_by_rank(y, l - 1, x, y);             // 再分割出l到r
                long long res = t[y].sum;                  // 获取区间和
                root[ver] = merge(merge(x, y), z);         // 恢复
                return res;
            }

            // 获取位置pos的值
            int get_val(int ver, int pos) {
                return _get_val(root[ver], pos);
            }

        private:
            // 创建新节点
            int new_node(int val) {
                t[++cnt] = {0, 0, val, rand(), 1, val, false};  // 初始化新节点
                return cnt;
            }

            // 克隆节点（用于可持久化）
            int clone(int p) {
                if (!p) return 0;
                t[++cnt] = t[p];  // 复制节点
                return cnt;
            }

            // 下传翻转标记
            void pushdown(int p) {
                if (!p || !t[p].rev) return;

                p = clone(p);  // 可持久化需要先克隆

                std::swap(t[p].l, t[p].r);  // 交换左右子树
                t[p].rev = false;           // 清除标记

                if (t[p].l) {
                    t[p].l = clone(t[p].l);  // 克隆左子树
                    t[t[p].l].rev ^= 1;     // 传递标记
                }
                if (t[p].r) {
                    t[p].r = clone(t[p].r);  // 克隆右子树
                    t[t[p].r].rev ^= 1;      // 传递标记
                }
            }

            // 更新子树大小和和
            void pushup(int p) {
                t[p].size = t[t[p].l].size + t[t[p].r].size + 1;
                t[p].sum = t[t[p].l].sum + t[t[p].r].sum + t[p].val;
            }

            // 按排名分割树（文艺平衡树需要按排名分割）
            void split_by_rank(int p, int rank, int &x, int &y) {
                if (!p) {
                    x = y = 0;
                    return;
                }
                pushdown(p);  // 下传翻转标记
                p = clone(p);  // 克隆节点

                if (t[t[p].l].size + 1 <= rank) {  // 当前节点在x树中
                    x = p;
                    split_by_rank(t[x].r, rank - t[t[p].l].size - 1, t[x].r, y);
                } else {  // 当前节点在y树中
                    y = p;
                    split_by_rank(t[y].l, rank, x, t[y].l);
                }
                pushup(p);  // 更新大小和和
            }

            // 合并两棵树
            int merge(int x, int y) {
                if (!x || !y) return x | y;

                pushdown(x);  // 下传标记
                pushdown(y);  // 下传标记

                if (t[x].key < t[y].key) {  // x优先级更高
                    x = clone(x);           // 克隆x
                    t[x].r = merge(t[x].r, y);  // y合并到x的右子树
                    pushup(x);
                    return x;
                } else {  // y优先级更高
                    y = clone(y);           // 克隆y
                    t[y].l = merge(x, t[y].l);  // x合并到y的左子树
                    pushup(y);
                    return y;
                }
            }

            // 查找第k小的值
            int _get_val(int p, int rank) {
                while (true) {
                    pushdown(p);  // 下传标记
                    if (rank <= t[t[p].l].size) {  // 在左子树中
                        p = t[p].l;
                    } else if (rank == t[t[p].l].size + 1) {  // 当前节点
                        return t[p].val;
                    } else {  // 在右子树中
                        rank -= t[t[p].l].size + 1;
                        p = t[p].r;
                    }
                }
            }
    };
}// namespace datastruct

using trix::readint;  // 使用trix命名空间中的readint

constexpr int MAXM = 1e6;
constexpr int MAXN = 1e6;
constexpr int MAXK = 1e6;

namespace examples{
    /*
    * 莫队使用示例：计算前缀亦或值，计算区间值并 O(1) 扩展
    */

    void work_mo_queue(){
        int n = readint();
        int m = readint();
        int k = readint();

        // 创建莫队实例
        DataStruct::MoAlgorithm<MAXN, MAXK> mo;
        mo.init(n, m, k);
        // 读取数组元素
        for (int i = 1; i <= n; ++i) {
            int val = readint();
            mo.addElement(i, val);
        }

        // 计算前缀异或
        mo.computePrefix();

        // 添加查询
        for (int i = 0; i < m; ++i) {
            int l = readint();
            int r = readint();
            mo.addQuery(i, l, r);
        }

        // 运行莫队算法
        mo.run();

        // 输出结果
        mo.printAnswers();
    }

    /*
    * 线段树使用示例：区间加法和区间查询
    * 1. 初始化线段树并构建
    * 2. 执行区间加法操作
    * 3. 执行区间查询操作
    */
    void work_segment_tree_add() {
        const int N = 1e5 + 10;
        static i64 a[N];

        int n = readint();  // 数组大小
        int m = readint();  // 操作次数

        // 读取初始数组
        for (int i = 1; i <= n; ++i) {
            a[i] = readint();
        }

        // 初始化线段树
        DataStruct::Segment_Tree_Segadd<N> seg;
        seg.build_tree(n, a);

        while (m--) {
            int op = readint();
            if (op == 1) {
                // 区间加法操作：将区间[l,r]每个元素加k
                int l = readint();
                int r = readint();
                int k = readint();
                seg.update(l, r, k);
            } else {
                // 区间查询操作：查询区间[l,r]的和
                int l = readint();
                int r = readint();
                i64 res = seg.query(l, r);
                printf("%lld\n", res);
            }
        }
    }

    /*
    * 线段树使用示例：区间覆盖和区间查询
    * 1. 初始化线段树并构建
    * 2. 执行区间覆盖操作
    * 3. 执行区间查询操作
    */
    void work_segment_tree_cover() {
        const int N = 1e5 + 10;
        static i64 a[N];

        int n = readint();  // 数组大小
        int m = readint();  // 操作次数

        // 读取初始数组
        for (int i = 1; i <= n; ++i) {
            a[i] = readint();
        }

        // 初始化线段树
        DataStruct::Segment_Tree_Segcover<N> seg;
        seg.build_tree(n, a);

        while (m--) {
            int op = readint();
            if (op == 1) {
                // 区间覆盖操作：将区间[l,r]每个元素设置为k
                int l = readint();
                int r = readint();
                int k = readint();
                seg.update(l, r, k);
            } else {
                // 区间查询操作：查询区间[l,r]的和
                int l = readint();
                int r = readint();
                i64 res = seg.query(l, r);
                printf("%lld\n", res);
            }
        }
    }

    /*
    * Treap使用示例：平衡树基本操作
    * 1. 插入元素
    * 2. 删除元素
    * 3. 查询排名
    * 4. 查询第k小元素
    * 5. 查询前驱
    * 6. 查询后继
    */
    void work_treap() {
        DataStruct::Treap treap;
        int n = readint();

        while (n--) {
            int op = readint();
            int x = readint();

            switch (op) {
                case 1:  // 插入x
                    treap.ins(x);
                    break;
                case 2:  // 删除x
                    treap.del(x);
                    break;
                case 3:  // 查询x的排名(比x小的数的个数+1)
                    printf("%d\n", treap.qrnk(x));
                    break;
                case 4:  // 查询排名为x的数
                    printf("%d\n", treap.qnum(x));
                    break;
                case 5:  // 查询x的前驱(小于x的最大数)
                    printf("%d\n", treap.qpre(x));
                    break;
                case 6:  // 查询x的后继(大于x的最小数)
                    printf("%d\n", treap.qsub(x));
                    break;
            }
        }
    }

    /*
    * FHQ-Treap使用示例：平衡树基本操作(非旋转实现)
    * 1. 插入元素
    * 2. 删除元素
    * 3. 查询排名
    * 4. 查询第k小元素
    * 5. 查询前驱
    * 6. 查询后继
    */
    void work_fhq_treap() {
        DataStruct::FHQTreap treap;
        int n = readint();

        while (n--) {
            int op = readint();
            int x = readint();

            switch (op) {
                case 1:  // 插入x
                    treap.ins(x);
                    break;
                case 2:  // 删除x
                    treap.del(x);
                    break;
                case 3:  // 查询x的排名(比x小的数的个数+1)
                    printf("%d\n", treap.qrnk(x));
                    break;
                case 4:  // 查询排名为x的数
                    printf("%d\n", treap.qnum(x));
                    break;
                case 5:  // 查询x的前驱(小于x的最大数)
                    printf("%d\n", treap.qpre(x));
                    break;
                case 6:  // 查询x的后继(大于x的最小数)
                    printf("%d\n", treap.qsub(x));
                    break;
            }
        }
    }

    /*
    * 可持久化FHQ-Treap使用示例：支持历史版本操作的平衡树
    * 1. 在指定版本插入元素
    * 2. 在指定版本删除元素
    * 3. 查询指定版本的排名
    * 4. 查询指定版本的第k小元素
    * 5. 查询指定版本的前驱
    * 6. 查询指定版本的后继
    */
    void work_persistent_fhq_treap() {
        DataStruct::PersistentFHQTreap treap;
        int n = readint();
        int current_ver = 0;  // 当前版本号

        while (n--) {
            int ver = readint();  // 基础版本
            int op = readint();
            int x = readint();
            current_ver++;  // 新版本号

            switch (op) {
                case 1:  // 在版本ver插入x，创建新版本current_ver
                    treap.insert(ver, current_ver, x);
                    break;
                case 2:  // 在版本ver删除x，创建新版本current_ver
                    treap.remove(ver, current_ver, x);
                    break;
                case 3:  // 查询版本ver中x的排名
                    printf("%d\n", treap.get_rank(ver, x));
                    break;
                case 4:  // 查询版本ver中排名为x的数
                    printf("%d\n", treap.get_val(ver, x));
                    break;
                case 5:  // 查询版本ver中x的前驱
                    printf("%d\n", treap.get_prev(ver, x));
                    break;
                case 6:  // 查询版本ver中x的后继
                    printf("%d\n", treap.get_next(ver, x));
                    break;
            }
        }
    }
}

int main() {
    #ifdef FILEIO
    file(std-datastruct);
    #endif

    #ifdef CPPIO
    std::cin.tie(0) -> sync_with_stdio(0);
    #endif

    /* 在这里编写你的代码 */

    return 0;
}