laekov

BZOJ2648 SJY摆棋子

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);

}


评论
热度(1)

© laekov | Powered by LOFTER