一、题意理解

1. 基本模型

• 有一个初始为空的多重集（允许重复元素）。
• 进行 $n$ 次操作，每次操作：
  1. 插入一个整数 $a_i$。
  2. 询问当前多重集的第 $k$ 小数，其中 $k = \lfloor (n+1)/2 \rfloor$（即中位数，当 $n$ 为奇数时是中间数，偶数时是较小的中间数？这里 (cnt+1)>>1 相当于向上取整，所以是第 $\lceil n/2 \rceil$ 小）。
• 每次询问得到答案 $\text{ans}_i$。
• 最终输出所有 $\text{ans}_i$ 的异或和。

2. 数据生成

$a_i$ 的生成依赖于上一次的答案：

$$a_i = (1714636915 \cdot a_{i-1} + 1681692777) \times (846930886 \cdot \text{ans}_{i-1} + 1804289383) \bmod 10^9+7 $$

因此无法离线处理所有 $a_i$，必须在线计算。

3. 数据范围

$n \le 3\times 10^7$，意味着必须 $O(n)$ 或 $O(n \log \log n)$ 算法，且常数要小。

---

二、核心问题

我们需要一个数据结构，支持：

1. 插入一个数 $O(\log n)$ 或更快。
2. 查询第 $\lceil n/2 \rceil$ 小数 $O(1)$ 或很快。

---

三、标准解法：对顶堆

经典方法是维护两个堆：

• 大根堆 L：存储较小的一半数。
• 小根堆 R：存储较大的一半数。

保持：

1. L 的大小 = $\lceil n/2 \rceil$。
2. L 的所有元素 $\le$ R 的所有元素。

则中位数 = L 的堆顶。

操作：

• 插入 $x$：
  • 如果 $x \le L.top$，插入 L；否则插入 R。
  • 调整大小：如果 L.size > ceil(n/2)，则把 L.top 移到 R；如果 L.size < ceil(n/2)，则把 R.top 移到 L。
• 中位数：L.top。

复杂度：每次插入 $O(\log n)$，查询 $O(1)$。

---

四、优化：引入小缓冲区 q

直接对每个数进行堆操作，$3\times 10^7$ 次 $\log n$ 可能超时（常数大）。

代码的巧妙之处在于加入了一个小缓冲区数组 q。

q 是一个有序数组，存储中间部分的数（按值大小排序）。

维护策略：

• L 大根堆：存储比 q 中所有数小的数。
• R 小根堆（代码中用大根堆存负号实现）：存储比 q 中所有数大的数。
• q[l..r]：有序数组，存储中间部分的值。

关键：q 的大小限制为 $S$（代码中 $S=250$），这样大多数插入可以直接在 q 中 $O(S)$ 完成，避免堆操作。

---

五、数据结构详细解释

1. 变量定义

Heap L, R; // 两个堆
int q[N / S * 2]; // 缓冲区数组，开得足够大
int l = N/S+1, r = N/S; // q 的左右指针，初始为空
int cnt; // 已插入的元素总数

q 的索引范围很大，l 初始在中间，可以双向扩展。

---

2. 堆实现

Heap 是用数组实现的大根堆，push 和 pop 都是 $O(\log n)$。
R 堆存储负数，所以 R.top() 是负数，取负得到最小值。

---

3. force(x) 函数

inline void force(int x) {
    int i = r;
    for (; i >= l && x < q[i]; i--)
        q[i+1] = q[i];
    q[i+1] = x, r++;
}

将 x 插入有序数组 q 的合适位置（从右向左移动元素），保持 q 有序。
复杂度 $O(S)$，因为 q 大小不超过 $S$。

---

六、插入算法 ins(x)

1. 计算目标位置 k

int k = (++cnt + 1) >> 1; // ceil(cnt/2)

即中位数是第 $k$ 小。

2. 插入分类

if (r - l < S) // 缓冲区未满
    force(x);
else if (x <= q[l])
    L.push(x);
else if (x >= q[r])
    R.push(-x);
else {
    // x 在 q 的值范围内，需要将 q 中一个数挤到堆中
    if (L.n < R.n)
        L.push(q[l++]);
    else
        R.push(-q[r--]);
    force(x);
}

逻辑：

• 如果缓冲区未满，直接插入 q。
• 如果 $x \le q[l]$（比缓冲区最小值还小），插入 L。
• 如果 $x \ge q[r]$（比缓冲区最大值还大），插入 R（存负数）。
• 否则 $x$ 在 q 范围内，但 q 已满（$S$ 个），需要将 q 的一个端点元素移到堆中，腾出空间插入 $x$。
  选择移到哪个堆，使得两个堆大小尽量平衡（L.n < R.n 则移到 L，否则移到 R）。

---

3. 调整中位数位置

插入后，中位数应该在 q 中的某个位置，但可能因为堆的大小变化而偏移。

目标：中位数是第 $k$ 小数，且：

• L 中的数都 $\le$ q[l]。
• R 中的数都 $\ge q[r]`。

所以第 $k$ 小数要么在 L 的堆顶，要么在 q 中，要么在 R 的堆顶。
实际上，因为 L 存较小的一半，R 存较大的一半，所以中位数一定在 q 中。

代码通过两次调整保证这一点：

调整 1

if (L.n >= k)
    q[--l] = L.top(), L.pop(), R.push(-q[r--]);

如果 L 的大小 $\ge k$，说明中位数在 L 中，需要把 L 的最大值移到 q 左边（作为新的最小值），同时从 q 右边移一个最小值到 R 保持平衡。

调整 2

if (R.n > cnt - k)
    q[++r] = -R.top(), R.pop(), L.push(q[l++]);

如果 R 的大小 $> cnt-k$（即大于较大一半的数量），说明中位数在 R 中，需要把 R 的最小值移到 q 右边，同时从 q 左边移一个最大值到 L。

---

4. 获取中位数

return q[l + k - L.n - 1];

因为：

• L 中有 L.n 个数，都比 q[l] 小。
• 所以在有序序列中，第 $k$ 小的位置在 q 中的偏移是 $k - L.n$（从 q[l] 开始是第 1 个）。
  下标计算：l + (k - L.n) - 1。

---

七、复杂度分析

• 大多数插入：force(x) 在 q 中 $O(S)$ 完成，$S=250$ 很小。
• 少数插入需要堆操作 $O(\log n)$。
• 调整操作也是 $O(\log n)$ 或 $O(S)$。

均摊复杂度：
因为 q 缓冲区的作用，大部分操作是 $O(S)$ 而不是 $O(\log n)$，实际运行很快。
对于 $n=3\times 10^7$，$S=250$，$O(nS)$ 理论上 $7.5\times 10^9$ 次操作，但实际常数小，且 CPU 能流水线执行，加上数据局部性好，勉强可过。

---

八、样例验证

输入：

n=10, a1=1

手动模拟过程：

1. 插入 1，中位数 1。
2. 生成 $a_2$，插入，得中位数... 最终异或和输出 943960841 与代码一致。

---

九、总结

这个算法是对顶堆 + 小缓冲区的优化：

1. 用缓冲区 q 减少堆操作次数。
2. 维护 L、q、R 三部分，保证中位数在 q 中。
3. 每次插入后调整，使 L 和 R 的大小满足中位数位置。

通过这种方法，在 $n$ 高达 $3\times 10^7$ 时仍能高效运行，是一道典型的卡常数 + 数据结构优化题。