问题重述

维护一个长度为 $n$ 的集合数组，支持三种操作和一个查询：

1. 插入操作（$a=1$）：给定 $r$，向第 $1$ 到第 $r$ 个集合插入元素 $i$（当前操作编号）
2. 翻转操作（$a=2$）：给定 $r$，翻转第 $1$ 到第 $r$ 个集合的顺序
3. 删除操作（$a=3$）：给定 $x$，从所有包含 $x$ 的集合中删除该元素
4. 查询操作：给定 $p$，输出第 $p$ 个集合中的最小元素（空集输出 $0$）

所有操作在线编码，需根据上一次答案实时解码。数据范围：$n, q \le 3 \times 10^5$。

核心挑战

与简单版相比，困难版的数据规模扩大到了 $3 \times 10^5$，简单版 $O(q\sqrt{q})$ 的分块算法会超时。需要更高效的数据结构。

解题思路：可持久化叶子平衡树

1. 为什么选择叶子平衡树（WBLT）？

• 叶子存储：只有叶子节点存储实际位置，内部节点只起结构作用
• 权重平衡：每个节点的左右子树大小满足 $size_{left} \ge \alpha \cdot size_{right}$，保证树高 $O(\log n)$
• 可持久化：支持高效的复制和修改

2. 数据结构设计

每个节点 $u$ 包含：

• ls, rs：左右子节点
• fa：一个队列，存储所有父节点（用于向上查找）
• val：如果是标记节点，存储元素值
• exit：节点状态（0=已删除，1=有效标记，2=内部节点）
• size：子树大小
• rev：翻转标记

关键创新：每个集合的元素信息分散存储在一棵树上：

• 叶子节点对应一个集合
• 内部节点维护一个懒标记集合 $S_u$，表示该子树中所有集合都包含 $S_u$ 中的元素
• 通过可持久化实现，每次操作只新建 $O(\log n)$ 个节点

3. 标记分解

将每个集合 $S_u$ 分解为：

$$S_u = T_u + \sum_{i=1}^k S_{v_{u,i}}$$

其中：

• $T_u$：直接存储在节点 $u$ 上的元素（通过 fa 队列指向标记节点）
• $v_{u,i}$：$u$ 的子节点
• 保持不变量：$\max(S_{v_{u,i}}) < \min(S_{v_{u,i+1}})$

核心操作实现

节点创建与管理

int newnode() {
    int u = ++tot;
    a[u].exit = 2;  // 标记为内部节点
    return u;
}

int newleaf() {
    int u = newnode();
    a[u].size = 1;
    return u;
}

int newtag(int x) {
    int u = ++tot;
    a[u].val = x;
    a[u].exit = 1;  // 标记为标记节点
    return u;
}

插入操作（Type 1）

目标：向前 $r$ 个集合插入元素 $i$

if (o == 1) {
    int p; cin >> p;
    p = (p + lastans - 1) % n + 1;
    auto [A, B] = split(rt, p);  // 分割成 [1..p] 和 (p..n]
    setT(A, id[i] = newtag(i));   // 向第一部分根节点添加标记
    rt = merge(A, B);              // 合并
}

关键点：

• split 操作将树按大小分割，返回左右子树
• setT 将标记节点加入根节点的 fa 队列
• 插入操作只修改 $O(\log n)$ 个节点

翻转操作（Type 2）

目标：翻转前 $r$ 个集合的顺序

if (o == 2) {
    int p; cin >> p;
    p = (p + lastans - 1) % n + 1;
    auto [A, B] = split(rt, p);
    setR(A);                      // 标记翻转
    rt = merge(A, B);
}

关键点：

• setR 只是打翻转标记，不实际修改结构
• 翻转标记在需要时会向下传递

删除操作（Type 3）

目标：删除元素 $x$

if (o == 3) {
    int x; cin >> x;
    x = (x + lastans - 1) % q + 1;
    a[id[x]].exit = 0;            // 标记标记节点为删除
}

关键点：

• 每个插入的元素对应一个标记节点 $id[x]$
• 删除只需将对应节点的 exit 设为 $0$
• 查询时会自动跳过已删除的元素

查询操作

目标：查询第 $p$ 个集合的最小元素

int p; cin >> p;
p = (p + lastans - 1) % n + 1;
int u = find(rt, p);              // 找到第 p 个叶子节点
cout << (lastans = get_val(u)) << '\n';  // 获取该集合的最小值

get_val 函数：递归查找最小元素

int get_val(int u) {
    if (a[u].exit == 0) return 0;           // 已删除
    if (a[u].val != 0) return a[u].val;     // 找到标记节点
    if (a[u].fa.empty()) return 0;          // 无父节点
    
    int ans = 0;
    while (1) {
        ans = get_val(a[u].fa.front());     // 递归查询父节点
        if (ans) return ans;
        if (a[u].fa.check()) break;         // 队列只剩一个元素
        a[u].fa.pop();                       // 弹出空标记
    }
    
    // 优化：如果节点不再需要，标记为删除
    if (a[u].exit == 1) {
        a[u].exit = 0;
        a[u].fa.pop();
        a[u].fa.clear();
    }
    return 0;
}

查找过程：

1. 从叶子节点 $u$ 开始
2. 检查 $u$ 是否直接存储了值（val 字段）
3. 否则，检查父节点队列中的标记节点
4. 由于标记节点的 val 是操作编号，且插入时间递增，所以先找到的一定是最小值
5. 递归过程中自动清理无效节点

WBLT 的平衡操作

权重平衡条件

constexpr double ALPHA = 0.292;
bool too_heavy(int sx, int sy) {
    return sy < ALPHA * (sx + sy);
}

条件：保证 $size_{left} \ge \alpha \cdot (size_{left} + size_{right})$ 且 $size_{right} \ge \alpha \cdot (size_{left} + size_{right})$

Merge 操作

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (too_heavy(a[x].size, a[y].size)) {
        auto [u, v] = cut(x);
        if (too_heavy(a[v].size + a[y].size, a[u].size)) {
            auto [z, w] = cut(v);
            return merge(merge(u, z), merge(w, y));
        } else {
            return merge(u, merge(v, y));
        }
    } else if (too_heavy(a[y].size, a[x].size)) {
        // 对称情况
    } else {
        return join(x, y);
    }
}

平衡策略：

• 如果 $x$ 太重，尝试旋转重新平衡
• 如果平衡，直接连接

Split 操作

pair<int, int> split(int x, int k) {
    if (!x) return {0, 0};
    if (!k) return {0, x};
    if (k == a[x].size) return {x, 0};
    
    auto [u, v] = cut(x);  // 临时分裂节点
    if (k <= a[u].size) {
        auto [w, z] = split(u, k);
        return {w, merge(z, v)};
    } else {
        auto [w, z] = split(v, k - a[u].size);
        return {merge(u, w), z};
    }
}

关键点：cut 操作临时解开节点，但不删除节点本身

复杂度分析

时间复杂度

• 插入/翻转：$O(\log n)$（WBLT 操作）
• 删除：$O(1)$（只修改标记）
• 查询：平均 $O(\log n)$
  • 向上递归 $O(\log n)$ 层
  • 每层检查 $O(1)$ 个标记
• 总复杂度：$O(q \log n + n)$

空间复杂度

• 每个操作创建 $O(\log n)$ 个新节点
• 总节点数：$O(q \log n + n)$
• 对于 $q \le 3 \times 10^5$，$\log n \approx 19$，节点数约 $6 \times 10^6$，可接受

优化技巧

1. 惰性标记：翻转操作只打标记，不实际修改
2. 队列维护：使用自定义队列（链表实现）避免 STL 开销
3. 节点复用：删除的节点标记为无效，但不立即回收
4. 平衡参数：$\alpha = 0.292$ 是经验最优值
5. 内存池：静态分配数组，避免动态内存分配

总结

本题的核心技术是可持久化叶子平衡树 + 懒标记集合：

1. 将集合元素分散存储在树节点的标记中
2. 利用插入操作的递增性，保证标记的自然有序
3. WBLT 提供 $O(\log n)$ 的分裂合并
4. 惰性删除和标记传播实现高效查询

这种设计使得原本需要维护 $n$ 个动态集合的问题，转化为维护一棵平衡树，极大降低了复杂度。