【bzoj2648】 SJY摆棋子

// bzoj2648
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 1<<30
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;

const int maxn=1000010,maxm=2;
int n,rt,K,ans,m;

struct KDtree {
	int v[maxm],mn[maxm],mx[maxm],l,r;
	friend bool operator < (const KDtree a,const KDtree b) {
		return a.v[K]<b.v[K];
	}
}tr[maxn],S;

void update(int k) {
	if (tr[k].l)
		for (int i=0;i<=1;i++) {
			tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].l].mx[i]);
			tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].l].mn[i]);
		}
	if (tr[k].r)
		for (int i=0;i<=1;i++) {
			tr[k].mx[i]=max(tr[k].mx[i],tr[tr[k].r].mx[i]);
			tr[k].mn[i]=min(tr[k].mn[i],tr[tr[k].r].mn[i]);
		}
}
int dis(KDtree a,KDtree b) {
	int res=0;
	for (int i=0;i<=1;i++) res+=abs(a.v[i]-b.v[i]);
	return res;
}
int eva(int k) {   //类似于估价函数，计算子树中可能的最短距离
	if (!k) return inf;
	int res=0;
	for (int i=0;i<=1;i++) res+=max(0,tr[k].mn[i]-S.v[i])+max(0,S.v[i]-tr[k].mx[i]);   //画个图YY一下，很有道理
	return res;
}
int build(int l,int r,int p) {
	K=p;
	int mid=(l+r)>>1;
	nth_element(tr+l,tr+mid,tr+r+1);
	for (int i=0;i<=1;i++) tr[mid].mn[i]=tr[mid].mx[i]=tr[mid].v[i];
	if (l<mid) tr[mid].l=build(l,mid-1,p^1);
	if (r>mid) tr[mid].r=build(mid+1,r,p^1);
	update(mid);
	return mid;
}
void insert(int k,int p) {
	K=p;
	if (S<tr[k]) {
		if (tr[k].l) insert(tr[k].l,p^1);
		else {
			tr[k].l=++n;tr[n]=S;
			for (int i=0;i<=1;i++) tr[n].mx[i]=tr[n].mn[i]=tr[n].v[i];
		}
	}
	else {
		if (tr[k].r) insert(tr[k].r,p^1);
		else {
			tr[k].r=++n;tr[n]=S;
			for (int i=0;i<=1;i++) tr[n].mx[i]=tr[n].mn[i]=tr[n].v[i];
		}
	}
	update(k);
}
void query(int k) {
	ans=min(ans,dis(S,tr[k]));   //更新答案
	int dl=eva(tr[k].l),dr=eva(tr[k].r);
	if (dl<dr) {
		if (dl<ans) query(tr[k].l);
		if (dr<ans) query(tr[k].r);
	}
	else {
		if (dr<ans) query(tr[k].r);
		if (dl<ans) query(tr[k].l);
	}
}
	
int main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d%d",&tr[i].v[0],&tr[i].v[1]);
	rt=build(1,n,0);
	for (int op,i=1;i<=m;i++) {
		scanf("%d%d%d",&op,&S.v[0],&S.v[1]);
		if (op==1) insert(rt,0);
		else {
			ans=inf;
			query(rt);
			printf("%d\n",ans);
		}
	}
	return 0;
}