嘟嘟嘟
我的做法是(cdq)分治。（因为不会(k-d tree)啊）
假设她站在点((x_0, y_0))，且对于任意的埋藏点((x_i, y_i))都满足(x_i leqslant x_0, y_i leqslant y_0)。则距离就可以化简为((x_0 - x_i) + (y_0 - y_i) = (x_0 + y_0) - (x_i + y_i))。
于是这就变成了陌上花开了人人都会做，唯一区别是用树状数组维护前缀最大值。
但是不一定所有点都满足在这个范围内啊。
于是就有一个比较暴力但是想法挺好的解决方法：每一次我们只统计((x_0 ,y_0))矩形范围内的点。然后把这些点每一次转(90)度，跑四遍(cdq)分治即可。
特别注意的一点是这个询问之前可能没有点，因此树状数组查完后要判断是否为(0)，只有有数的时候才更新。
复杂度还是比较高的，某谷开了氧气才过。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 3e5 + 5;
const int maxy = 1e6 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, m, Maxx = 0, Maxy = 0;
struct Node
{
int x, y, id;
}b[maxn << 1], a[maxn << 1], t[maxn << 1];
int cnt = 0, ans[maxn];
int c[maxy];
int lowbit(int x)
{
return x & -x;
}
void erase(int pos)
{
for(; pos <= Maxy; pos += lowbit(pos))
if(c[pos]) c[pos] = 0;
else break;
}
void add(int pos, int d)
{
for(; pos <= Maxy; pos += lowbit(pos)) c[pos] = max(c[pos], d);
}
int query(int pos)
{
int ret = 0;
for(; pos; pos -= lowbit(pos)) ret = max(ret, c[pos]);
return ret;
}
void cdqSolve(int L, int R)
{
if(L == R) return;
int mid = (L + R) >> 1, id1 = L, id2 = mid + 1;
cdqSolve(L, mid); cdqSolve(mid + 1, R);
for(int i = L; i <= R; ++i)
{
if(id2 > R || (id1 <= mid && a[id1].x <= a[id2].x))
{
t[i] = a[id1++];
if(!t[i].id) add(t[i].y, t[i].x + t[i].y);
}
else
{
t[i] = a[id2++];
if(t[i].id)
{
int tp = query(t[i].y);
if(tp) ans[t[i].id] = min(ans[t[i].id], t[i].x + t[i].y - tp);
}
}
}
for(int i = L; i <= mid; ++i) if(!a[i].id) erase(a[i].y);
for(int i = L; i <= R; ++i) a[i] = t[i];
}
int main()
{
Mem(ans, 0x3f);
n = read(); m = read();
for(int i = 1; i <= n; ++i)
{
int x = read() + 1, y = read() + 1;
Maxx = max(Maxx, x); Maxy = max(Maxy, y);
b[i] = (Node){x, y, 0};
}
for(int i = 1; i <= m; ++i)
{
int op = read(), x = read() + 1, y = read() + 1;
Maxx = max(Maxx, x); Maxy = max(Maxy, y);
b[i + n] = (Node){x, y, op == 2 ? ++cnt : 0};
}
Maxx++; Maxy++;
for(int i = 1; i <= n + m; ++i) a[i] = b[i];
cdqSolve(1, n + m);
for(int i = 1; i <= n + m; ++i) a[i] = b[i], a[i].x = Maxx - a[i].x;
cdqSolve(1, n + m);
for(int i = 1; i <= n + m; ++i) a[i] = b[i], a[i].y = Maxy - a[i].y;
cdqSolve(1, n + m);
for(int i = 1; i <= n + m; ++i) a[i] = b[i], a[i].x = Maxx - a[i].x, a[i].y = Maxy - a[i].y;
cdqSolve(1, n + m);
for(int i = 1; i <= cnt; ++i) write(ans[i]), enter;
return 0;
}