题意

$m$ 次操作，支持加入点，查询所有加入的点到某个点的曼哈顿距离最小值。

定义 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的曼哈顿距离是 $|x_1-x_2|+|y_1-y_2|$。

分析

不难注意到，我们可以大力分讨，查询的时候查询在左下角，左上角，右下角，右上角四个方位的最小距离，这样子可以消掉绝对值。现在以左下角为例，考虑怎么求。

我们现在就是求在查询操作之前且 $x_1<x,y_1<y$ 的 $x_1+y_1$ 的最大值。这实际上是一个三位偏序，离线下来用 cdq 分治即可。时间复杂度 $O(n\log^2n)$。

其余位置可以用 $(M-x,y),(x,M-y),(M-x,M-y)$ 直接求得，这里 $M$ 是坐标上限。

但是这里有一些细节要处理。

• 只有修改操作的点才可以加入树状数组，查询的点是不行的。
• 树状数组要初始化为负无穷，如果是 $0$ 会默认加入了点 $(0,0)$。

然后大力谴责出题人卡常。

T 飞了，要卡常。

• cdq 分治的时候每一层都要排序，考虑上一层已经排完序了，可以归并排序，直接用 C++ 自带的 merge(bg_1,ed_1,bg_2,ed_2,bg_3)，这个函数可以将两个有序数列有序合并。
• 如果当前不是查询操作，不用移动另一个指针，可以优化后面一段没有查询操作的情况。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 1000005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, m, ans[N], op[N], tr[N];
const int M = 1e6;
struct Point{
    int x, y, id;
}p[N], q[N], a[N];
bool operator <(const Point &a, const Point &b){return a.x != b.x ? a.x < b.x : a.y != b.y ? a.y < b.y : a.id < b.id;}
il void add(int x, int k){for (int i = x; i <= M; i += (i & (-i))) tr[i] = max(tr[i], k);}
il int ask(int x){int ans = -1e9;for (int i = x; i >= 1; i -= (i & (-i))) ans = max(ans, tr[i]);return ans;}
il void clr(int x){for (int i = x; i <= M; i += (i & (-i))) tr[i] = -1e9;}
void cdq(int l, int r){
    if (l == r) return ;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    int j = l;
    for (int i = mid + 1; i <= r; i++) if (op[p[i].id]){
        for (; j <= mid && p[j].x <= p[i].x; j++) if (!op[p[j].id]) add(p[j].y, p[j].x + p[j].y);
        ans[p[i].id] = min(ans[p[i].id], p[i].x + p[i].y - ask(p[i].y));
    }
    for (int i = l; i < j; i++) if (!op[p[i].id]) clr(p[i].y);
    merge(p + l, p + mid + 1, p + mid + 1, p + r + 1, q + l);
    for (int i = l; i <= r; i++) p[i] = q[i];
}
signed main(){
    n = rd(), m = rd();
    for (int i = 1; i <= M; i++) tr[i] = -1e9;
    for (int i = 1; i <= n; i++) a[i] = Point{rd() + 1, rd() + 1, i}, ans[i] = 1e9;
    for (int i = n + 1; i <= n + m; i++) op[i] = rd() - 1, a[i] = Point{rd() + 1, rd() + 1, i}, ans[i] = 1e9;
    for (int i = 1; i <= n + m; i++) p[i] = Point{a[i].x, a[i].y, i};
    cdq(1, n + m);
    for (int i = 1; i <= n + m; i++) p[i] = Point{M - a[i].x, a[i].y, i};
    cdq(1, n + m);
    for (int i = 1; i <= n + m; i++) p[i] = Point{a[i].x, M - a[i].y, i};
    cdq(1, n + m);
    for (int i = 1; i <= n + m; i++) p[i] = Point{M - a[i].x, M - a[i].y, i};
    cdq(1, n + m);
    for (int i = n + 1; i <= n + m; i++) if (op[i]) printf ("%d\n", ans[i]);
    return 0;
}