P11210 『STA - R8』强制在线动态二维数点

> 数据结构界的最新成果！强制在线动态二维数点已经可以做到线性时间！

要拿到图灵奖，你需要解决下面这道动态在线二维数点问题： 平面上有 $n$ 个点 $(x_i,y_i)$，**排列在 $\bm{y=x}$ 的直线下方（即，$\bm{y_i\le x_i}$ 成立）**。 我会进行 $q$ 次操作，操作有两种类型： 1. 修改操作 `U i x y`：令 $x_i:=x,y_i:=y$。（即，将 $x_i$ 和 $y_i$ 分别赋值为 $x$ 和 $y$。） 2. 询问操作 `Q l r`：给出一个**四个顶点分别是 $\bm{(l,l),(r,l),(l,r),(r,r)}$ 的矩形**，求出在给出的矩形内的点 $^\dagger$ $(x,y)$ 中最小的 $x-y$ 的值。**特别地，规定当矩形没有包含任何一个点时答案为 $\bm{0}$。** 两种操作会以某种方式进行加密，详细要求见下方【输入格式】一栏。 $^\dagger$：点 $(x,y)$ 在 $(l,l),(r,l),(l,r),(r,r)$ 所构成的矩形内，当且仅当 $l\le x\le r$ 且 $l\le y\le r$。

无

无

对于所有测试数据，$1\le n,q\le 5\times 10^5$，并且保证解密后的 $1\le l\le r\le n$ 且 $1\le i\le n$，$1\le y\le x\le n$。 **本题采用捆绑测试，并开启子任务依赖。** - Subtask 0（5 points）：$n,q\le 5\times 10^3$。 - Subtask 1（20 points）：无修改操作。 - Subtask 2（25 points）：满足特殊性质。 - Subtask 3（20 points）：$n,q\le 10^5$。 - Subtask 4（30 points）：无特殊限制。 特殊性质（数据随机）：操作类型、修改的位置、初始时和修改后的点的坐标和询问区间（参数 $(i,x,y),(l,r)$ 的值）在合法范围内独立地均匀随机生成。