问题分析

我们需要支持两种操作：

1. 插入：在二维点 $(x, y)$ 放置 $v$ 瓶水（每个位置只会被放置一次）
2. 查询：在矩形区域 $[x_1, x_2] \times [y_1, y_2]$ 中，找到瓶数的第k大值

特点：

• 在线：需要异或上次答案
• 数据范围大：$n \leq 5\times 10^5$，$q \leq 10^5$
• 每个位置只插入一次

---

核心难点

这是一个带插入的二维区间第k大查询问题，比普通区间第k大更复杂，因为：

• 是二维空间
• 有插入操作
• 需要在线

---

解法1：权值线段树套线段树（树套树）

思路

• 外层：权值线段树（维护瓶数 $v$）
• 内层：动态开点线段树（维护 $y$ 坐标）
• 内层线段树的每个节点再维护一个动态开点线段树（维护 $x$ 坐标）

实际上更常用的是：

• 外层：权值线段树（维护 $v$ 的分布）
• 内层：二维线段树或线段树套平衡树（维护坐标）

操作流程

插入 $(x, y, v)$：

1. 在外层权值线段树中，找到 $v$ 对应的叶子节点
2. 沿着路径更新所有内层树，在内层树中插入点 $(x, y)$

查询第k大：

1. 在外层权值线段树上二分
2. 对于当前权值 $mid$，查询内层树中矩形 $[x_1, x_2] \times [y_1, y_2]$ 内的点数
3. 如果右子树的点数 $\geq k$，则第k大在右子树；否则在左子树找第 $(k - 右子树点数)$ 大

复杂度

• 插入：$O(\log n \log n)$
• 查询：$O(\log n \log n \log n)$（需要二分）
• 空间：$O(q \log^2 n)$

---

解法2：K-D Tree + 平衡树

思路

• 用 K-D Tree 维护所有插入的点（按 $(x, y)$ 坐标）
• 每个 K-D Tree 节点维护子树内所有 $v$ 值的平衡树

查询第k大

1. 在 K-D Tree 上查询矩形 $[x_1, x_2] \times [y_1, y_2]$ 内的所有点
2. 将这些点的 $v$ 值收集起来，用平衡树或堆找第k大

优化：直接在 K-D Tree 节点上维护权值线段树，查询时合并。

---

解法3：整体二分 + 二维数点

这是更优美的解法：

思路

• 将所有操作（插入和查询）放在一起按时间排序
• 对权值进行整体二分

过程

设当前二分权值范围 $[l, r]$，处理操作序列 $[ql, qr]$：

1. 令 $mid = \lfloor \frac{l+r}{2} \rfloor$
2. 扫描操作：
   • 插入操作：如果 $v > mid$，在二维数据结构中插入点 $(x, y)$
   • 查询操作：查询矩形内点数 $cnt$
     • 如果 $cnt \geq k$，说明答案在 $[mid+1, r]$ 中
     • 否则答案在 $[l, mid]$ 中，且 $k = k - cnt$
3. 递归处理两个子问题

二维数据结构选择

• 动态二维数点可以用 CDQ分治 或 树状数组套线段树
• 由于有插入，适合用带修莫队或分块，但二维分块较复杂

---

样例解析

输入：

10 7
1 1 1 1
1 2 2 3  
1 4 1 2
1 3 4 4
2 1 1 4 1 3  # 查询[1,4]×[1,1]中第3大 → 只有1个点{1}，不存在第3大
2 2 2 3 5 4  # 查询[2,3]×[2,5]中第4大 → 只有点{(2,2):3}，不存在第4大  
2 2 1 4 4 2  # 查询[2,4]×[1,4]中第2大 → 有点{(2,2):3, (3,4):4, (4,1):2}，排序[4,3,2]，第2大=3

输出：

NAIVE!ORZzyz.
NAIVE!ORZzyz.
3

---

实现建议

对于本题数据范围：

• 推荐整体二分 + 树状数组套线段树，代码相对可写
• 或者使用 K-D Tree 暴力查询，在数据随机时表现良好
• 注意在线处理：所有输入坐标要异或 lastans

---

复杂度对比

方法	插入复杂度	查询复杂度	空间复杂度	实现难度
树套树	$O(\log^2 n)$	$O(\log^3 n)$	$O(q\log^2 n)$	高
K-D Tree	$O(\log n)$	$O(\sqrt{n})$	$O(q)$	中
整体二分	$O(\log^2 n)$		$O(q\log n)$

---

总结

这道题是二维平面动态第k大的经典问题，考察高级数据结构的应用。整体二分是较优美的解法，将动态问题转化为静态问题处理，降低了实现难度。