Log^2的cdq分治怎么也跑不过。优化常数优化到底了也不行。所以kd大法好。
怎么都觉得kd树就一暴力+剪枝=log。
思想就是先按x二分，然后再按y二分，然后再按x二分。然后这玩意比较像平衡树，中间那个点是要代表一个真实的结点的而不是一个值。然后insert的时候感觉复杂度完全没有保证啊。如果要保证可能要替罪羊一类的东西吧。虽然这题好像不用保证。
询问的时候就更迷了，就是估计一个离哪边近，然后先搜。然后另一边如果估计值还小于答案就再搜一遍。好诡异，时间复杂度是怎么来的。
然后代码略丑，加了zhx式读入优化后长度xxxxx。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define READ_OPTIMIZE
#ifdef READ_OPTIMIZE
/*int _d_;
#define readInt(_s_) {\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}*/
const int BUF_SIZE = 30;
char buf[BUF_SIZE], *buf_s = buf, *buf_t = buf + 1;
#define PTR_NEXT() \
{ \
buf_s ++; \
if (buf_s == buf_t) \
{ \
buf_s = buf; \
buf_t = buf + fread(buf, 1, BUF_SIZE, stdin); \
} \
}
#define readInt(_n_) \
{ \
while (*buf_s != '-' && !isdigit(*buf_s)) \
PTR_NEXT(); \
bool register _nega_ = false; \
if (*buf_s == '-') \
{ \
_nega_ = true; \
PTR_NEXT(); \
} \
int register _x_ = 0; \
while (isdigit(*buf_s)) \
{ \
_x_ = _x_ * 10 + *buf_s - '0'; \
PTR_NEXT(); \
} \
if (_nega_) \
_x_ = -_x_; \
(_n_) = (_x_); \
}
#else
#define readInt(_s_) (scanf("%d",&_s_));
#endif
#define min(_a_,_b_) (((_a_)<(_b_))?(_a_):(_b_))
#define max(_a_,_b_) (((_a_)>(_b_))?(_a_):(_b_))
struct point {
int x, y, t;
};
struct kdnode {
int x, y;
int l, r, u, d;
kdnode *ls, *rs;
kdnode() {
ls = 0, rs = 0;
}
};
const int maxn = 1000009;
const int maxnd = maxn;
const int inf = 0x3f3f3f3f;
inline bool cmpx(const point& a, const point& b) {
return a. x < b. x;
}
inline bool cmpy(const point& a, const point& b) {
return a. y < b. y;
}
int m, n;
point a[maxn], b[maxn];
kdnode *sp, nlst[maxnd];
inline void update(kdnode*& p) {
p-> l = p-> x;
p-> r = p-> x;
p-> d = p-> y;
p-> u = p-> y;
if (p-> ls) {
if (p-> ls-> l < p-> l)
p-> l = p-> ls-> l;
if (p-> ls-> r > p-> r)
p-> r = p-> ls-> r;
if (p-> ls-> d < p-> d)
p-> d = p-> ls-> d;
if (p-> ls-> u > p-> u)
p-> u = p-> ls-> u;
}
if (p-> rs) {
if (p-> rs-> l < p-> l)
p-> l = p-> rs-> l;
if (p-> rs-> r > p-> r)
p-> r = p-> rs-> r;
if (p-> rs-> d < p-> d)
p-> d = p-> rs-> d;
if (p-> rs-> u > p-> u)
p-> u = p-> rs-> u;
}
}
kdnode *kdBuild(int l, int r, int dr = 1) {
if (l >= r)
return 0;
int mid = (l + r) >> 1;
kdnode *p = sp ++;
if (dr)
nth_element(a + l, a + mid, a + r, cmpx);
else
nth_element(a + l, a + mid, a + r, cmpy);
p-> x = a[mid]. x;
p-> y = a[mid]. y;
p-> ls = kdBuild(l, mid, dr ^ 1);
p-> rs = kdBuild(mid + 1, r, dr ^ 1);
update(p);
return p;
}
inline int guessDist(kdnode* p, int x, int y) {
int ans = 0;
if (x > p-> r)
ans += x - p-> r;
else if (x < p-> l)
ans += p-> l - x;
if (y > p-> u)
ans += y - p-> u;
else if (y < p-> d)
ans += p-> d - y;
return ans;
}
void kdQry(kdnode* p, int x, int y, int& ans) {
int dl, dr, d = abs(x - p-> x) + abs(y - p-> y);
if (d < ans)
ans = d;
if (p-> ls)
dl = guessDist(p-> ls, x, y);
else
dl = inf;
if (p-> rs)
dr = guessDist(p-> rs, x, y);
else
dr = inf;
if (dl < dr) {
if (dl < ans)
kdQry(p-> ls, x, y, ans);
if (dr < ans)
kdQry(p-> rs, x, y, ans);
}
else {
if (dr < ans)
kdQry(p-> rs, x, y, ans);
if (dl < ans)
kdQry(p-> ls, x, y, ans);
}
}
kdnode* kdIns(kdnode* p, int x, int y, int dr = 1) {
if (!p) {
p = sp ++;
p-> x = x;
p-> y = y;
p-> ls = 0;
p-> rs = 0;
}
else {
if (dr) {
if (x < p-> x)
p-> ls = kdIns(p-> ls, x, y, dr ^ 1);
else
p-> rs = kdIns(p-> rs, x, y, dr ^ 1);
}
else {
if (y < p-> y)
p-> ls = kdIns(p-> ls, x, y, dr ^ 1);
else
p-> rs = kdIns(p-> rs, x, y, dr ^ 1);
}
}
update(p);
return p;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
readInt(m);
readInt(n);
for (int i = 0; i < m; ++ i) {
readInt(a[i]. x);
readInt(a[i]. y);
a[i]. t = 0;
}
for (int i = 0; i < n; ++ i) {
readInt(b[i]. t);
readInt(b[i]. x);
readInt(b[i]. y);
}
sp = nlst;
kdnode *rt = kdBuild(0, m);
for (int i = 0; i < n; ++ i)
if (b[i]. t == 2) {
int ans = inf;
kdQry(rt, b[i]. x, b[i]. y, ans);
printf("%d\n", ans);
}
else
rt = kdIns(rt, b[i]. x, b[i]. y);
}