看时间比较宽么，写一个log^2的cdq+树状数组么。
然后被2648卡了。学kd-tree吧。
naive。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
int _d_;
#define readInt(_s_) {\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
struct point {
int x, y, t, i;
};
const int maxn = 500009;
const int maxz = 1000009;
const int inf = 0x3f3f3f3f;
inline bool cmpPoint(const point& a, const point& b) {
return a. x < b. x;
}
int maxa;
struct pbt {
int t[maxz], r[maxz], ttm;
void init() {
memset(r, 0, sizeof(r));
ttm = 0;
}
inline void next() {
++ ttm;
}
void chg(int p, int v) {
for (; p < maxa; p += (p & -p))
if (r[p] == ttm)
t[p] = max(t[p], v);
else
r[p] = ttm, t[p] = v;
}
int qry(int p) {
int s = -inf;
for (; p; p -= (p & -p))
if (r[p] == ttm)
s = max(t[p], s);
return s;
}
};
int m, n, ans[maxn];
point a[maxn], b[maxn], tmp[maxn];
pbt tu, td;
void calcEff(point* a, int l, int p, int q) {
tu. next();
td. next();
for (int i = 0, j = p; j < q; ++ j) {
for (; i < l && a[i]. x <= b[j]. x; ++ i) {
tu. chg(maxa - a[i]. y, a[i]. x - a[i]. y);
td. chg(a[i]. y, a[i]. x + a[i]. y);
}
int vu = b[j]. x - b[j]. y - tu. qry(maxa - b[j]. y);
int vd = b[j]. x + b[j]. y - td. qry(b[j]. y);
int vn = min(vu, vd);
ans[b[j]. i] = min(ans[b[j]. i], vn);
}
tu. next();
td. next();
for (int i = l - 1, j = q - 1; j >= p; -- j) {
for (; i >= 0 && a[i]. x >= b[j]. x; -- i) {
tu. chg(maxa - a[i]. y, -a[i]. x - a[i]. y);
td. chg(a[i]. y, -a[i]. x + a[i]. y);
}
int vu = - b[j]. x - b[j]. y - tu. qry(maxa - b[j]. y);
int vd = - b[j]. x + b[j]. y - td. qry(b[j]. y);
int vn = min(vu, vd);
ans[b[j]. i] = min(ans[b[j]. i], vn);
}
}
int cdq(int l, int r) {
if (l + 1 == r) {
if (b[l]. t == 2)
return r;
else
return l;
}
int mid = (l + r) >> 1;
int xl = cdq(l, mid);
int xr = cdq(mid, r);
calcEff(b + xl, mid - xl, mid, xr);
int tx = l, ty;
for (int i = l, j = mid; i < xl || j < xr;)
if (j == xr || (i < xl && b[i]. x < b[j]. x))
tmp[tx ++] = b[i ++];
else
tmp[tx ++] = b[j ++];
ty = tx;
for (int i = xl, j = xr; i < mid || j < r;)
if (j == r || (i < mid && b[i]. x < b[j]. x))
tmp[ty ++] = b[i ++];
else
tmp[ty ++] = b[j ++];
for (int i = l; i < r; ++ i)
b[i] = tmp[i];
return tx;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
tu. init();
td. init();
readInt(m);
readInt(n);
maxa = 0;
for (int i = 0; i < m; ++ i) {
readInt(a[i]. x);
readInt(a[i]. y);
maxa = max(maxa, max(a[i]. x, a[i]. y));
}
for (int i = 0; i < n; ++ i) {
readInt(b[i]. t);
readInt(b[i]. x);
readInt(b[i]. y);
maxa = max(maxa, max(b[i]. x, b[i]. y));
b[i]. i = i;
if (b[i]. t == 2)
ans[i] = inf;
else
ans[i] = -1;
}
++ maxa;
int x = cdq(0, n);
sort(a, a + m, cmpPoint);
calcEff(a, m, 0, x);
for (int i = 0; i < n; ++ i)
if (ans[i] > -1)
printf("%d\n", ans[i]);
}