题意：
二维平面上有若干个点。
现在要维护一种数据结构，支持插入一个点以及询问其余点到某个点的最小曼哈顿距离。
思路：
这是个\(kdtree\)模板题。
\(kdtree\)是一种可以高效处理\(k\)维空间信息的结构。一般我们遇到的是\(2\)维空间或者\(3\)维空间。
一般用来解决的问题为：空间最近点对、空间第\(k\)远点对、矩阵查询等问题，这些问题离线可以离线\(cdq\)解决，但是用\(kdtree\)的话可以在线处理这些问题。
一般认为一次操作期望复杂度是\(\sqrt{n}\)的，但最坏情况下复杂度为\(O(n)\)。所以我们其实可以将它看作一种玄学且比较优美的暴力~一般我们都直接定义全局变量然后大力减枝。
开局建颗树，减枝刷题数！
回到这个题，查询的话\(ans\)注意是全局变量。另外还定义了一个估价函数，含义是到达那个矩形内部的最好情况，显然这个最好情况如果都大于目前的\(ans\)，我们可以不用搜索该子树。
如果类似于一个圆就可能被卡到\(O(n^2)\)
细节见代码：
/*
* Author: heyuhhh
* Created Time: 2019/11/22 14:12:30
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#define MP make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define INF 0x3f3f3f3f
#define Local
#ifdef Local
#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)
void err() { std::cout << '\n'; }
template<typename T, typename...Args>
void err(T a, Args...args) { std::cout << a << ' '; err(args...); }
#else
#define dbg(...)
#endif
void pt() {std::cout << '\n'; }
template<typename T, typename...Args>
void pt(T a, Args...args) {std::cout << a << ' '; pt(args...); }
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
//head
const int N = 1e6 + 5;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n, m;
int D;
const int dim = 2;
struct Point {
int d[2], mn[2], mx[2], l, r;
int& operator [] (int x) {return d[x];}
Point(int x = 0, int y = 0) {
l = r = 0;
d[0] = x; d[1] = y;
}
}p[N >> 1];
bool operator < (Point A, Point B) {
return A[D] < B[D];
}
struct kdtree {
int rt, ans; //注意ans定义为全局变量
Point tree[N], T;
void upd(int o) {
Point ls = tree[tree[o].l], rs = tree[tree[o].r];
for(int i = 0; i < dim; i++) {
if(tree[o].l) {
tree[o].mn[i] = min(tree[o].mn[i], ls.mn[i]);
tree[o].mx[i] = max(tree[o].mx[i], ls.mx[i]);
}
if(tree[o].r) {
tree[o].mn[i] = min(tree[o].mn[i], rs.mn[i]);
tree[o].mx[i] = max(tree[o].mx[i], rs.mx[i]);
}
}
}
int build(int l, int r, int now) {
D = now;
int mid = (l + r) >> 1;
nth_element(p + l, p + mid, p + r + 1);
tree[mid] = p[mid];
for(int i = 0; i < dim; i++) {
tree[mid].mn[i] = tree[mid].mx[i] = tree[mid][i];
}
if(l < mid) tree[mid].l = build(l, mid - 1, now ^ 1);
if(r > mid) tree[mid].r = build(mid + 1, r, now ^ 1);
upd(mid);
return mid;
}
void insert(int o, int now) {
D = now;
if(T[D] < tree[o][D]) {
if(tree[o].l) insert(tree[o].l, now ^ 1);
else {
tree[o].l = ++n;
tree[n] = T;
for(int i = 0; i < dim; i++) {
tree[n].mx[i] = tree[n].mn[i] = T[i];
}
}
} else {
if(tree[o].r) insert(tree[o].r, now ^ 1);
else {
tree[o].r = ++n;
tree[n] = T;
for(int i = 0; i < dim; i++) {
tree[n].mx[i] = tree[n].mn[i] = T[i];
}
}
}
upd(o);
}
int dis(Point A, Point B) {
int res = 0;
for(int i = 0; i < dim; i++) {
res += abs(A[i] - B[i]);
}
return res;
}
int get(Point A, Point B) {//估价函数
int res = 0;
for(int i = 0; i < dim; i++) {
res += max(0, A[i] - B.mx[i]) + max(0, B.mn[i] - A[i]);
}
return res;
}
void query(int o) {
ans = min(ans, dis(tree[o], T));
int l = INF, r = INF;
if(tree[o].l) l = get(T, tree[tree[o].l]);
if(tree[o].r) r = get(T, tree[tree[o].r]);
if(l < r) {
if(l < ans) query(tree[o].l);
if(r < ans) query(tree[o].r);
} else {
if(r < ans) query(tree[o].r);
if(l < ans) query(tree[o].l);
}
}
}kd;
void run(){
n = read(), m = read();
for(int i = 1; i <= n; i++) {
int x = read(), y = read();
p[i] = Point(x, y);
}
kd.rt = kd.build(1, n, 0);
while(m--) {
int t = read(), x = read(), y = read();
kd.T = Point(x, y);
if(t == 1) {
kd.insert(kd.rt, 0);
} else {
kd.ans = INF;
kd.query(kd.rt);
printf("%d\n", kd.ans);
}
}
}
int main() {
run();
return 0;
}