问题重述

我们维护一个长度为 $n$ 的集合数组，初始全为空。需要在线处理 $q$ 次操作，每次操作包含：

1. 修改操作（三种类型）：

   • 插入操作（$a=1$）：给定 $r$，向第 $1$ 到第 $r$ 个集合中插入元素 $i$（$i$ 是当前操作编号）
   • 翻转操作（$a=2$）：给定 $r$，翻转第 $1$ 到第 $r$ 个集合的顺序
   • 删除操作（$a=3$）：给定 $x$，从所有包含元素 $x$ 的集合中删除该元素

2. 查询操作：给定 $p$，输出第 $p$ 个集合中的最小元素（空集输出 $0$）

所有操作都经过在线编码，需要根据上一次的答案实时解码。

核心挑战

• 在线操作：必须实时响应
• 数据规模：$n, q \le 10^5$
• 操作复杂度：直接模拟会导致 $O(nq)$ 不可行
• 翻转操作：会使维护变得复杂

解题思路：分块处理

将操作序列按块大小 $B$ 分块，每 $B$ 个操作为一个轮次。

为什么选择 $B = \sqrt{q}$？

• 操作总数为 $q$，块数为 $\frac{q}{B}$
• 每块内需要 $O(B)$ 时间处理
• 总复杂度 $O(q \cdot \frac{q}{B} + q \cdot B) = O(q\sqrt{q})$，当 $B = \sqrt{q}$ 时最优

数据结构设计

1. 核心概念

• 位置序列：维护一个长度为 $n$ 的数组 $p[1..n]$，表示当前第 $i$ 个位置对应的是原始数组的第 $p[i]$ 个集合
• 块结构：将位置序列分成若干段（segment），每段是位置序列的一个连续区间
• 每个段维护：
  • 区间范围 $[tl, tr]$（在 $p$ 数组中的下标）
  • 翻转标记 $rev$（True 表示该段是反向的）
  • 一个队列 $tq$，记录本轮插入到该段的所有元素

2. 辅助结构

• $ed[x]$：标记元素 $x$ 是否已被删除
• $vq[x]$：存储包含元素 $x$ 的所有段（用于快速查询）
• $wp$：临时的位置数组，用于重建

操作处理

插入操作（$a=1$）

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

// 遍历所有段，找到第 r 个集合所在的位置
int s = 0;
for (int j: cur) {
    int len = tr[j] - tl[j] + 1;  // 当前段的长度
    s += len;
    if (s >= r) {
        // 如果 r 落在当前段中间，需要分裂该段
        if (s > r) {
            // 创建新段，存储后半部分
            tot++;
            tq[tot] = tq[j];
            int g = s - r;  // 后半部分的长度
            if (rev[tot] = rev[j]) {
                // 段方向相同的情况
                tl[tot] = tl[j];
                tr[tot] = (tl[j] += g) - 1;
            } else {
                // 段方向相反的情况
                tr[tot] = tr[j];
                tl[tot] = (tr[j] -= g) + 1;
            }
            cur.insert(next(find(all(cur), j)), tot);
        }
        // 向前 r 个集合插入元素 i
        tq[j].push(i);
        break;
    }
    // 整个段都在前 r 个集合内，全部插入
    tq[j].push(i);
}

关键点：

• 插入操作是惰性的：只将元素加入段的队列，不立即更新位置数组
• 段分裂：当 $r$ 落在段中间时，将段一分为二

翻转操作（$a=2$）

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

int s = 0, sz = 0;
for (int j: cur) {
    sz++;
    int len = tr[j] - tl[j] + 1;
    s += len;
    if (s >= r) {
        // 如果需要，先分裂段
        if (s > r) {
            // 分裂逻辑同插入操作
            // ...
        }
        // 翻转前 sz 个段
        reverse(cur.begin(), cur.begin() + sz);
        // 翻转这些段的 rev 标记
        for (int k = 0; k < sz; k++) {
            rev[cur[k]] ^= true;
        }
        break;
    }
}

关键点：

• 只翻转段的顺序和标记，不实际移动元素
• 时间复杂度 $O(B)$，因为一次翻转最多涉及 $B$ 个段

删除操作（$a=3$）

if (x < i) ed[x] = true;  // 标记元素 x 为已删除

关键点：

• 删除是惰性的：只打标记，不立即从队列中移除
• 注意 $x$ 是操作编号，必须小于当前操作编号（只能删除之前插入的元素）

查询操作

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

int query(int p) {
    // 1. 找到第 p 个位置所属的段
    int s = 0;
    for (int i: cur) {
        s += tr[i] - tl[i] + 1;
        if (s >= p) {
            // 计算在段内的具体位置
            int g = s - p + 1;  // 从右往左数的位置
            int pos;
            if (rev[i]) {
                // 段是反向的
                pos = p[tl[i] + g - 1];
            } else {
                // 段是正向的
                pos = p[tr[i] - g + 1];
            }
            
            // 2. 从该段的队列中找最小未被删除的元素
            // 首先检查包含该位置的所有段（可能有多个？）
            while (vq[pos].size()) {
                int tmp = qq(vq[pos].front());
                if (tmp) return tmp;
                vq[pos].pop();
            }
            return qq(i);
        }
    }
    return 0;
}

关键点：

• 先定位到具体位置，再查找该位置对应的段
• 使用 $vq$ 数组快速定位包含某个原始位置的所有段
• $qq$ 函数负责从队列中弹出已删除的元素

重建机制

当一个轮次结束时（$cur$ 的大小达到 $B$），需要进行重建：

if (cur.size() >= B) {
    int cnt = 0;
    // 1. 根据当前段的顺序和方向，重建位置数组 p
    for (int j: cur) {
        if (rev[j]) {
            // 反向遍历
            for (int k = tr[j]; k >= tl[j]; k--) {
                vq[wp[++cnt] = p[k]].push(j);
            }
        } else {
            // 正向遍历
            for (int k = tl[j]; k <= tr[j]; k++) {
                vq[wp[++cnt] = p[k]].push(j);
            }
        }
    }
    // 2. 更新 p 数组
    for (int j = 1; j <= n; j++) {
        p[j] = wp[j];
    }
    // 3. 重置 cur，用一个段表示整个序列
    cur.clear();
    cur.push_back(++tot);
    tl[tot] = 1;
    tr[tot] = n;
    rev[tot] = false;
}

重建的作用：

• 将惰性操作的效果真正应用到位置数组上
• 重置段结构，防止段数量无限增长
• 保证每 $B$ 次操作至少重建一次

复杂度分析

时间复杂度

• 每轮处理：$O(B)$ 次操作，每次操作 $O(B)$ 个段 ⇒ $O(B^2)$
• 轮次数：$\frac{q}{B}$
• 总复杂度：$O(\frac{q}{B} \cdot B^2) = O(qB) = O(q\sqrt{q})$

具体操作分析：

• 插入/翻转：$O(B)$（遍历段）
• 删除：$O(1)$
• 查询：$O(B)$（遍历段 + 队列操作）
• 重建：$O(n + B)$

空间复杂度

• 每个元素最多存在于一个段的队列中：$O(q)$
• $p$ 数组：$O(n)$
• $cur$ 数组：$O(B)$
• 总空间：$O(n + q + \sqrt{q})$

优化技巧

1. 选择 $B = \sqrt{q}$：平衡时空复杂度
2. 惰性删除：避免频繁从队列中移除元素
3. 段分裂：减少不必要的元素移动
4. 定期重建：防止段数量过多
5. 使用 std::queue：保证 $O(1)$ 的队首访问

总结

本题的核心思想是分块 + 惰性操作：

1. 将操作序列分块，每块内维护段结构
2. 修改操作只更新段的标记和队列
3. 查询时实时计算答案，从队列中找出最小元素
4. 定期重建，保证数据结构不退化

这种方法将 $O(nq)$ 的暴力优化到 $O(q\sqrt{q})$，在 $n,q \le 10^5$ 的范围内可行。