laekov

看时间比较宽么，写一个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]);

}