强制在线动态二维数点

zhenjianuo2025 · 2024-09-26 09:13:08 · 题解

将 (y,x) 的点视作 [x,y] 的区间，现在问题转化为维护区间集合 S，支持：

• 动态修改 S 中的某个元素；
• 查询 S 内被给定区间 [l,r] 包含的区间中最短的区间。

对于一次询问操作 [l,r]：

• 找到 x_0\ge l 的最小的 y_0；
• 求出 y_0\le y\le r 的最小的 y-x 的值。

可以证明这是正确的：

• 一方面，对于任何合法的区间 [x,y]，因为 y\ge y_0，必定会被计入答案之中。
• 另一方面，考虑一个 y_0\le y\le r 且 x<l 的不合法区间 [x,y]，由于 y-x>y_0-l\ge y_0-x_0，所以必定不会对答案造成任何影响。

上面两项都可以使用线段树简单维护。用 std::mutiset 辅助存储每个左端点对应的右端点集，以及每个右端点对应的左端点集。修改时单点修改两棵线段树上的对应位置。时间复杂度 \Theta\left((n+q)\log n\right)，可以通过。

其他任何想法欢迎与我私信交流。