在 1145141919810 天前，SX 看了看 cdq 分治和整体二分，照着题解打了代码，照着代码理解了下这两种东西是干嘛用的。
然后他就自信的以为自己理解了这两种东西。
其实不然，啥叫你对着代码懂了代码你就懂了这个的原理啊，我的评价是 sx 就是依托答辩（确信
链接 Link
题目描述很清晰，这是在一个二维平面上，每次有两种操作：
- 新添加一个点。
- 询问距离点 \((x, y)\) 曼哈顿距离最小的点。
先简化问题，考虑不带修，只有 2 操作的版本，这个时候我们发现这个问题不好做，我们再简化问题（雾），把它简化到一维上去，也就是一根线段上。如果现在有一根线段，线段上有一些点，然后每次询问一个点 \(x\) 距离它最小距离的点是啥，这个时候这个问题就非常智力残障，对原有的点排个序，二分它的前驱后继。
那回到二维的版本，一维的操作给了我们启发，首先我们在一维，每个点有前驱后继。在二维，一个点把整个平面分成了四个象限，我们就拿第三象限举例，因为剩下三个象限与第三象限情况差不多，只要把坐标反转一下就好了，而且第三象限中，\(x' < x, y' < y\)，这看上去非常的顺眼（雾），让我们很想去维护（究极雾）。
那么我们的问题就变成了：在一个二维平面上，有 \(n\) 个点，第 \(i\) 个点坐标为 \((x_i, y_i)\)，\(m\) 个询问每次查询距离 \((x, y)\) 曼哈顿距离最近的点 \(k\) 且 \(x_k < x, y_k < y\)。
三个约束条件：\(x_k < x, y_k < y\)，还要最小化 \(x - x_k + y - x_k = (x+y) - (x_k + y_k)\)（分离已知项和未知项）我们不难想到令 \(w_k = (x_k + y_k)\)，那么实际上这里就是让我们求 \(x_k < x, y_k < y\) 的最大的 \(w_k\)。
根据一维的方法，我们不难想到以 \(x\) 为第一关键字排序。当然这样不行，对所有输入和查询的点都存下来，离线，再按照 \(x\) 为第一关键字排序，依次处理就行了。如此以来就可以暴保证所有的点都是 \(x_k < x\) 的。不看第一维，我们的问题就变成了：求一个 \(k\) 满足 \(y_k < y\) 且 \(w_k\) 最大。
不难想到维护一个数组 \(g\)，\(g[i] = \max{w_k(y_k = i)}\)（因为有可能很多的 \(y_k\) 相等）每次要查询 \([0, y - 1]\) 的 \(g\) 前缀最大值。显而易见用树状数组线段树都行。时间复杂度 \(O((n + m)\log_2 n)\)
这块扯这么长是因为这是我这种幼儿园智力障碍小朋友的思考过程，大佬估计一眼就秒了 qwq
下面考虑动态的带修问题。首先来思考一下，假设多了一个点 \((x', y')\) 会造成哪些影响？
对于第二维度 \(y\) 当然很好维护，但是它的前提 \(x\) 有序不在了。如果我们新加入一个点 \((x', y')\)，它会不会对后面的点造成影响，会的。对哪些点？\(x_i < x'\) 的。这怎么维护？你让我维护这个东西，没有这个能力好吧，再输就输越南了（划掉
cdq 分治妙在对时间来做分治。为什么是时间呢？比如说我们有个修改，在第 \(i\) 刻，那么 \(i - 1\) 刻前的所有查询不受影响，该怎么来还是怎么来，\(i + 1\) 后的就要记录它的影响。那么对于 \(i + 1\) 后的所有查询，我们只需要更新这一个点的贡献即可。
问题出在这里：我们可能会有很多个点都要更新。cdq 分治的思想在于，对于每个时间段 \([l, r]\)，先单纯地计算 \([1, mid]\)（可以看成，对于 \(m\) 条操作，我们只做 \(1\sim mid\) 条操作的结果），然后再计算 \([mid + 1, r]\) 的答案（同上），然后我们拿 \([l, mid]\) 里面的修改，去更新 \([mid + 1, r]\) 的已经求出来的答案。
拿上面这题炒栗子。由于我们是分治处理的，用我们刚刚做静态问题的思路，我们默认 \([l, mid]\)，\([mid + 1, r]\) 的 \(x\) 是有序的。然后我们就可以用线性复杂度合并这两个有序的序列，像归并排序一样。有没有发现现在我们和最初的静态问题一样了！我们仍然可以挨个扫描这个点的序列，然后加点，查询，就和静态问题一样！
然后……就没了吧 qwq
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAXN 1000000
#define QWQ cout << "QWQ" << endl;
using namespace std;
int f = 0;
int INF;
struct node {
int opt, x, y, id;
} a[MAXN + 10];
//qaq
int tr[MAXN + 10];
int lowbit(int x) {
return x & (-x);
}
int n;
void change(int x, int y) {
for(int p = y; p <= 1000000; p += lowbit(p))
tr[p] = max(tr[p], x + y);
}
int query(int x) {
int res = 0;
while(x) {
res = max(res, tr[x]);
x -= lowbit(x);
}
return res;
}
void clear(int pos) {
for(; pos <= 1000000; pos += lowbit(pos))
tr[pos] = 0;
}
//qwq
node tmp[MAXN + 10];
int ans[MAXN + 10];
void sto_cdq_orz(int l, int r) {
if(l >= r) return ;
int mid = (l + r) >> 1;
sto_cdq_orz(l, mid);
sto_cdq_orz(mid + 1, r);
int pos = l, p = mid + 1, c = l - 1;
while(pos <= mid && p <= r) {
if(a[pos].x <= a[p].x) {
if(a[pos].opt == 1) change(a[pos].x, a[pos].y);
tmp[++c] = a[pos], pos++;
}
else {
if(a[p].opt == 2) {
int qaq = query(a[p].y);
if(qaq) ans[a[p].id] = min(ans[a[p].id], a[p].x + a[p].y - qaq);
}
tmp[++c] = a[p], p++;
}
}
while(pos <= mid) tmp[++c] = a[pos], pos++;
while(p <= r) {
if(a[p].opt == 2) {
int qaq = query(a[p].y);
if(qaq) ans[a[p].id] = min(ans[a[p].id], a[p].x + a[p].y - qaq);
}
tmp[++c] = a[p], p++;
}
for(int p = l; p <= r; p++) a[p] = tmp[p];
for(int p = l; p <= r; p++)
if(a[p].opt == 1) clear(a[p].y);
return ;
}
//
node qwq[MAXN + 10];
void init() {
int m;
cin >> n >> m;
for(int p = 1, x, y; p <= n; p++) {
cin >> x >> y;
x++, y++;
a[p].opt = 1, a[p].x = x, a[p].y = y;
}
for(int p = 1, opt, x, y; p <= m; p++) {
cin >> a[++n].opt >> a[n].x >> a[n].y;
a[n].x++, a[n].y++;
if(a[n].opt == 2) f++, a[n].id = f;
}
for(int p = 1; p <= n; p++)
qwq[p] = a[p];
}
void work() {
memset(ans, 0x7f, sizeof(ans));
memset(ans, 0x3f, sizeof(ans));
sto_cdq_orz(1, n);
for(int p = 1; p <= n; p++) a[p] = qwq[p], a[p].x = 1000001 - a[p].x;
sto_cdq_orz(1, n);
for(int p = 1; p <= n; p++) a[p] = qwq[p], a[p].y = 1000001 - a[p].y;
sto_cdq_orz(1, n);
for(int p = 1; p <= n; p++) a[p] = qwq[p], a[p].x = 1000001 - a[p].x, a[p].y = 1000001 - a[p].y;
sto_cdq_orz(1, n);
}
int main() {
init();
work();
for(int p = 1; p <= f; p++)
cout << ans[p] << endl;
}
