最近学了 cdq 分治想来做做这道题，结果被有些毒瘤的代码恶心到了。 /ll

题目大意：一开始给定一些平面中的点。然后给定一些修改和询问：

• 修改：增加一个点。
• 询问：给定一个点，求离这个点最近（定义为曼哈顿距离最小）的点离这个点的曼哈顿距离。（注意这个点并不加入平面）

其他细节详见 题目传送门 。

显然一开始给定的点可以看作是一开始的修改。现在就只有修改和查询了。

发现这里的曼哈顿距离有两个绝对值，考虑拆一下绝对值，显然我们可以拆出这个式子：

• 如果 $A_x\le B_x,A_y\le B_y$，也就是 $A$ 在平面上面的距离在 $B$ 的左下方，则 $A$ 和 $B$ 的距离 $\text{dist}(A,B)=(B_x+B_y)-(A_x+A_y)$。

那么该怎么处理其他方面的点呢：左上方、右下方、右上方？？？从左下方通过坐标变换旋转一下就可以同样处理了。所以我们现在只需要处理 $A$ 在 $B$ 的左下方的情况即可！

发现在这个式子里面，$A$ 和 $B$ 是独立的。如果 $B$ 是一个询问的点，那么在其左下方的点中（$A_x\le B_x,A_y\le B_y$），若要使其询问的答案最小，显然需要使 $A_x+A_y$ 的值最大，这个是可以预处理出来的。

而且还需要保证 $A$ 的出现时间在 $B$ 的前面。

这个时候我们梳理一下在 $A$ 在 $B$ 左下方的这种情况下，$A$ 对 $B$ 产生贡献的条件当且仅当：

• $A_t\le B_t$，也就是 $A$ 在 $B$ 前面出现。
• $A_x\le B_x,A_y\le B_y$，也就是 $A$ 在 $B$ 左下方。

这不就是三维偏序吗！！！！所以直接使用 cdq 三维偏序即可。

代码可能有点难写，但是有很长一段都是很基础的。

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;struct que {bool f;int id, x, y;
} ori[N], val[N], a[N];
int n, m;
int mx = 0, my = 0;
int ans[N];bool cmp1(que x, que y) {if (x.id != y.id)return x.id < y.id;if (x.x != y.x)return x.x < y.x;return x.y < y.y;
}bool cmp2(que x, que y) {return x.x < y.x;
}struct BIT {int tree[N];void clear(int pos) {for (; pos <= my; pos += pos & -pos)if (tree[pos])tree[pos] = 0;elsereturn ;}void add(int pos, int val) {for (; pos <= my; pos += pos & -pos)tree[pos] = max(tree[pos], val);}int query(int pos) {int ans = 0;for (; pos; pos -= pos & -pos)ans = max(ans, tree[pos]);return ans;}
} st;void cdq(int l, int r) {if (l + 1 == r)return ;int mid = (l + r) / 2;cdq(l, mid);sort(val + l, val + mid, cmp2);sort(val + mid, val + r, cmp2);int pos = l;for (int i = mid; i < r; i++) {if (val[i].f)continue;for (; pos < mid && val[pos].x <= val[i].x; pos++)if (val[pos].f)st.add(val[pos].y, val[pos].x + val[pos].y);int x = st.query(val[i].y);if (x > 0)ans[val[i].id] = min(ans[val[i].id], val[i].x + val[i].y - x);}for (int i = l; i <= pos; i++)st.clear(val[i].y);copy(ori + l, ori + r, val + l);cdq(mid, r);
}int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {int x, y;cin >> x >> y, x++, y++;ori[i] = {1, i, x, y};mx = max(mx, x), my = max(my, y);}for (int i = 1; i <= m; i++) {int op, x, y;cin >> op >> x >> y;x++, y++;mx = max(mx, x), my = max(my, y);if (op == 1)ori[i + n] = {1, i + n, x, y};elseori[i + n] = {0, i + n, x, y};}n += m, mx++, my++;for (int i = 1; i <= n; i++)ans[i] = 1e9;copy(ori + 1, ori + n + 1, a + 1);//cdqsort(ori + 1, ori + n + 1, cmp1);copy(ori + 1, ori + n + 1, val + 1);cdq(1, n + 1);//---copy(a + 1, a + n + 1, ori + 1);for (int i = 1; i <= n; i++)ori[i].x = mx - ori[i].x;sort(ori + 1, ori + n + 1, cmp1);copy(ori + 1, ori + n + 1, val + 1);cdq(1, n + 1);//---copy(a + 1, a + n + 1, ori + 1);for (int i = 1; i <= n; i++)ori[i].y = my - ori[i].y;sort(ori + 1, ori + n + 1, cmp1);copy(ori + 1, ori + n + 1, val + 1);cdq(1, n + 1);//---copy(a + 1, a + n + 1, ori + 1);for (int i = 1; i <= n; i++)ori[i].x = mx - ori[i].x, ori[i].y = my - ori[i].y;sort(ori + 1, ori + n + 1, cmp1);copy(ori + 1, ori + n + 1, val + 1);cdq(1, n + 1);for (int i = 1; i <= n; i++)if (a[i].f == 0)cout << ans[i] << endl;return 0;
}