大概思路就是嗯 K-D Tree 之后在每个点记个子树内最大坐标剪枝，带重构的写法，WA1234, T5678910

这里是代码，楼主先润去睡觉了，大概明天晚上回来看/kel（）

// #pragma GCC optimize(1)
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast", "inline", "-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second
const int N = 6e5 + 10;
PII s[N];
const double alpha = 0.75;
struct Node
{
    int L, R, U, D, s[2], sz, d;
} tr[N];
int n, m, cnt = 0, rt, g[N], t = 0, res;

inline bool cmp1(int x, int y)
{
    return s[x].x < s[y].x;
}

inline bool cmp2(int x, int y)
{
    return s[x].y < s[y].y;
}

inline int dist(int x, PII y)
{
    return abs(s[x].x - y.x) + abs(s[x].y - y.y);
}

inline void pushup(int x)
{
    Node &root = tr[x], l = tr[root.s[0]], r = tr[root.s[1]];
    root.L = root.R = s[x].x, root.U = root.D = s[x].y, root.sz = l.sz + r.sz + 1;
    if(root.s[0])
        root.D = min(root.D, l.D), root.U = max(root.U, l.U),
        root.L = min(root.L, l.D), root.R = max(root.R, l.R);
    if(root.s[1])   
        root.D = min(root.D, r.D), root.U = max(root.U, r.U),
        root.L = min(root.L, r.D), root.R = max(root.R, r.R);
    return ;
}

inline int build(int l, int r)
{
    if(l > r) return 0;
    int mid = l + r >> 1;
    double avx = 0, avy = 0, vax = 0, vay = 0;
    for(int i(l); i <= r; ++ i) avx += s[g[i]].x, avy += s[g[i]].y;
    avx /= 1.00 * (r - l + 1), avy /= 1.00 * (r - l + 1);
    for(int i(l); i <= r; ++ i) vax += 1.00 * (s[g[i]].x - avx) * (s[g[i]].x - avx), vay += 1.00 * (s[g[i]].y - avy) * (s[g[i]].y - avy);
    if(vax >= vay) nth_element(g + l, g + mid, g + r + 1, cmp1), tr[g[mid]].d = 1;
    else nth_element(g + l, g + mid, g + r + 1, cmp2), tr[g[mid]].d = 0; 
    tr[g[mid]].s[0] = build(l, mid - 1), tr[g[mid]].s[1] = build(mid + 1, r), pushup(g[mid]);
    return g[mid];
}

inline bool heavy(int x)
{
    Node root = tr[x], l = tr[root.s[0]], r = tr[root.s[1]];
    return (1.00 * l.sz > alpha * root.sz) or (1.00 * r.sz > alpha * root.sz);
}

inline void print(int x)
{
    if(tr[x].s[0]) print(tr[x].s[0]);
    g[++ t] = x;
    if(tr[x].s[1]) print(tr[x].s[1]);
    return ;
}

inline void Rebuild(int &x)
{
    t = 0, print(x), x = build(1, t);
    return ;
}

inline void insert(int &x, int p)
{
    if(x == 0)
    {
        x = p, pushup(x);
        return ;
    }
    if(tr[x].d)
        if(s[p].x <= s[x].x) insert(tr[x].s[0], p);
        else insert(tr[x].s[1], p);
    else   
        if(s[p].y <= s[x].y) insert(tr[x].s[0], p);
        else insert(tr[x].s[1], p);
    pushup(x);
    if(heavy(x)) Rebuild(x);
    return ;
}

inline int f(int p, int x, int y)
{
    Node t = tr[p]; int ret = 0;
    if(x < t.L) ret += (t.L - x);
    if(x > t.R) ret += (x - t.R);
    if(y < t.D) ret += (t.D - y);
    if(y > t.U) ret += (y - t.U);
    return ret; 
}

inline void query(int p, int x, int y)
{
    if(f(p, x, y) > res) return ;
    res = min(res, dist(p, make_pair(x, y)));
    int distl = f(tr[p].s[0], x, y), distr = f(tr[p].s[1], x, y);
    if(distl < res and distr < res)
        if(distl < distr)
        {
            query(tr[p].s[0], x, y);
            if(distr < res) query(tr[p].s[1], x, y);
        }
        else
        {
            query(tr[p].s[1], x, y);
            if(distl < res) query(tr[p].s[0], x, y);
        }
    else
    {
        if(distl < res) query(tr[p].s[0], x, y);
        if(distr < res) query(tr[p].s[1], x, y);
    }
    return ;
}

int main()
{
    scanf("%d %d", &n, &m), cnt = n;
    for(int i(1); i <= n; ++ i) scanf("%d %d", &s[i].x, &s[i].y), insert(rt, i);
    for(int t, x, y; m -- ; )
    {
        scanf("%d %d %d", &t, &x, &y);
        if(t == 1) s[++ cnt] = make_pair(x, y), insert(rt, cnt);
        else res = INT_MAX, query(rt, x, y), printf("%d\n", res);
    }
    return 0;
}

顺便拜谢帮忙调的神犇/bx