k-d tree + 重构的思想，就能卡过luogu和bzoj啦orz
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, rot, nowD, opt, uu, vv, ans, rub[1000005], din, cur;
const double aph=0.65;
struct Point{
int d[2], mn[2], mx[2], l, r, siz;
int & operator[](int x){
return d[x];
}
bool operator<(const Point &x)const{
return d[nowD]<x.d[nowD];
}
Point(int x=0, int y=0){
l = r = siz = 0;
d[0] = x; d[1] = y;
}
}p[1000005];
int getDis(Point x, Point y){
return abs(x[1]-y[1])+abs(x[0]-y[0]);
}
struct KDTree{
Point t[1000005], T;
void pushUp(int x){
Point l=t[t[x].l], r=t[t[x].r];
for(int i=0; i<2; i++){
t[x].mn[i] = t[x].mx[i] = t[x][i];
if(t[x].l){
t[x].mn[i] = min(t[x].mn[i], l.mn[i]);
t[x].mx[i] = max(t[x].mx[i], l.mx[i]);
}
if(t[x].r){
t[x].mn[i] = min(t[x].mn[i], r.mn[i]);
t[x].mx[i] = max(t[x].mx[i], r.mx[i]);
}
}
t[x].siz = l.siz + r.siz + 1;
}
int newNode(){
if(din) return rub[din--];
else return ++cur;
}
int build(int l, int r, int now){
nowD = now;
int mid=(l+r)>>1, k=newNode();
nth_element(p+l, p+mid, p+1+r);
t[k] = p[mid];
t[k].l = t[k].r = t[k].siz = 0;
if(l<mid) t[k].l = build(l, mid-1, now^1);
if(mid<r) t[k].r = build(mid+1, r, now^1);
pushUp(k);
return k;
}
void pia(int k, int num){
if(t[k].l) pia(t[k].l, num);
p[num+t[t[k].l].siz+1] = t[k];
rub[++din] = k;
if(t[k].r) pia(t[k].r, num+t[t[k].l].siz+1);
}
void chkPia(int &k, int now){
if(aph*t[k].siz<t[t[k].l].siz || aph*t[k].siz<t[t[k].r].siz){
pia(k, 0);
k = build(1, t[k].siz, now);
}
}
void insert(int &k, int now){
if(!k){
k = newNode();
t[k] = T;
t[k].l = t[k].r = 0;
pushUp(k);
return ;
}
if(T[now]>=t[k][now]) insert(t[k].r, now^1);
else insert(t[k].l, now^1);
pushUp(k);
chkPia(k, now);
}
int get(int k, Point p){
int re=0;
for(int i=0; i<2; i++)
re += max(0, p[i]-t[k].mx[i]);
for(int i=0; i<2; i++)
re += max(0, t[k].mn[i]-p[i]);
return re;
}
void query(int k, int now){
int d=getDis(t[k],T), dl=0x3f3f3f3f, dr=0x3f3f3f3f;
ans = min(ans, d);
if(t[k].l) dl = get(t[k].l, T);
if(t[k].r) dr = get(t[k].r, T);
if(dl<dr){
if(dl<ans) query(t[k].l, now^1);
if(dr<ans) query(t[k].r, now^1);
}
else{
if(dr<ans) query(t[k].r, now^1);
if(dl<ans) query(t[k].l, now^1);
}
}
}kdt;
void rn(int &x){
char ch=getchar();
x = 0;
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
x = x * 10 + ch - '0';
ch = getchar();
}
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++){
rn(p[i][0]);
rn(p[i][1]);
}
rot = kdt.build(1, n, 0);
while(m--){
scanf("%d %d %d", &opt, &uu, &vv);
kdt.T = Point(uu, vv);
if(opt==1)
kdt.insert(rot, 0);
else{
ans = 0x3f3f3f3f;
kdt.query(rot, 0);
printf("%d
", ans);
}
}
return 0;
}