# 2. 题解

KD-Tree 还是很吼滴！

（其中黑色线是矩形，红色是询问的坐标点，蓝色线是距离，而第三个距离为 0）

#include <bits/stdc++.h>

#define NS (500005)
#define DS (2)
#define AS (0.75)

using namespace std;

template <typename _Tp>inline void IN (_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, m, root, sz, D;

stack<int> rub;

int MKN()
{
if (rub.empty()) return ++sz;
int tmp = rub.top(); rub.pop(); return tmp;
}

struct node
{
int d[DS], mx[DS], mn[DS], l, r, sz;
int& operator [] (int a) {return d[a];}
bool operator < (node another)const {return d[D] < another[D];}
}arr[NS << 1], e[NS << 1];

void pup(int a)
{
node l = e[e[a].l], r = e[e[a].r];
for (int i = 0; i < DS; i += 1)
{
e[a].mx[i] = e[a].mn[i] = e[a][i];
if (e[a].l)
{
e[a].mx[i] = max(e[a].mx[i], l.mx[i]);
e[a].mn[i] = min(e[a].mn[i], l.mn[i]);
}
if (e[a].r)
{
e[a].mx[i] = max(e[a].mx[i], r.mx[i]);
e[a].mn[i] = min(e[a].mn[i], r.mn[i]);
}
}
e[a].sz = l.sz + r.sz + 1;
}

int Build(int l, int r, int d = 0)
{
if (l > r) return 0;
D = d;
int a = MKN(), mid = ((l + r) >> 1);
nth_element(arr + l, arr + mid, arr + r + 1);
e[a] = arr[mid];
e[a].l = Build(l, mid - 1, (d + 1) % DS);
e[a].r = Build(mid + 1, r, (d + 1) % DS);
pup(a); return a;
}

void rec(int a,int tot = 0)
{
if (!a) return;
rec(e[a].l, tot), tot += e[e[a].l].sz + 1;
arr[tot] = e[a], rub.push(a);
rec(e[a].r, tot);
}

void check(int& a, int d)
{
if (e[e[a].l].sz > e[a].sz * AS || e[e[a].r].sz > e[a].sz * AS)
rec(a), a = Build(1, e[a].sz, d);
}

void insert(node T, int& a = root, int d = 0)
{
if (!a)
{
a = MKN(), e[a] = T, e[a].l = e[a].r = 0, pup(a);
return;
}
if (T[d] < e[a][d]) insert(T, e[a].l, (d + 1) % DS);
else insert(T, e[a].r, (d + 1) % DS);
pup(a), check(a, d);
}

int dis(node T, int a)
{
int tot = 0;
for (int i = 0; i < DS; i += 1)
tot += abs(T[i] - e[a][i]);
return tot;
}

int get_dis(node T, int a)
{
int tot = 0;
for (int i = 0; i < DS; i += 1)
tot += max(e[a].mn[i] - T[i], 0) + max(T[i] - e[a].mx[i], 0);
return tot;
}

void query(node T, int& ans, int a = root)
{
ans = min(ans, dis(T, a));
int dl = INT_MAX, dr = INT_MAX;
if (e[a].l) dl = get_dis(T, e[a].l);
if (e[a].r) dr = get_dis(T, e[a].r);
if (dl < dr)
{
if (dl < ans) query(T, ans, e[a].l);
if (dr < ans) query(T, ans, e[a].r);
}
else
{
if (dr < ans) query(T, ans, e[a].r);
if (dl < ans) query(T, ans, e[a].l);
}
}

int main(int argc, char const* argv[])
{
IN(n), IN(m);
for (int i = 1; i <= n; i += 1)
for (int j = 0; j < DS; j += 1)
IN(arr[i][j]);
root = Build(1, n);
while (m--)
{
int opt, a, b, ans = INT_MAX;
IN(opt), IN(a), IN(b);
if (opt == 1) insert((node){a,b});
else printf("%d\n", (query((node){a,b}, ans), ans));
}
return 0;
}