最近學了 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;
}