Chaos Slover 补档计划 - K-D Tree

2015.11.29 14:40 Sun| 5 visits oi_2016| ChaosSlover补档计划| Text

BZOJ2648&2716 [Violet 3]天使玩偶

天呐!BZOJ2716 这良心大样例真是吓到我了。

K-D 树真是一个好东西。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;

#define N 500005
#define inf 0x3f3f3f3f

int n, dem, q;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct point
{
    int x, y;
    point() {}
    point(int _x, int _y) : x(_x), y(_y) {}
    bool operator <(const point &p) const
    { return dem ? y < p.y : x < p.x; }
    inline friend int dist(point p1, point p2)
    { return abs(p1.x - p2.x) + abs(p1.y - p2.y); }
} p[N];

struct node
{
    node *son[2];
    point p; int l, r, d, u;

    node() {}
    node(point _p) : p(_p) { l = r = p.x; d = u = p.y; }

    inline void pushup()
    {
        if (son[0])
            l = min(l, son[0]->l), r = max(r, son[0]->r),
            d = min(d, son[0]->d), u = max(u, son[0]->u);
        if (son[1])
            l = min(l, son[1]->l), r = max(r, son[1]->r),
            d = min(d, son[1]->d), u = max(u, son[1]->u);
    }

    int mind(point _p)
    {
        int re = 0;
        if (_p.x < l) re += l - _p.x;
        else if (_p.x > r) re += _p.x - r;
        if (_p.y < d) re += d - _p.y;
        else if (_p.y > u) re += _p.y - u;
        return re;
    }
};

node *root;

node *build(point p[], int l, int r, int d)
{
    if (l > r) return NULL;
    int mid = (l + r) >> 1;
    dem = d;
    nth_element(p + l, p + mid, p + r + 1);
    node *re = new node(p[mid]);
    re->son[0] = build(p, l, mid - 1, d ^ 1);
    re->son[1] = build(p, mid + 1, r, d ^ 1);
    re->pushup();
    return re;
}

void insert(node *&pos, point p, int d)
{
    if (!pos) { pos = new node(p); return; }
    dem = d;
    if (p < pos->p) insert(pos->son[0], p, d ^ 1);
    else insert(pos->son[1], p, d ^ 1);
    pos->pushup();
}

int query(node *pos, point p)
{
    int re = dist(pos->p, p);
    int d[2] = {pos->son[0] ? pos->son[0]->mind(p) : inf,
                pos->son[1] ? pos->son[1]->mind(p) : inf};
    int t = d[0] > d[1];
    if (d[t] < re) re = min(re, query(pos->son[t], p));
    if (d[t ^ 1] < re) re = min(re, query(pos->son[t ^ 1], p));
    return re;
}

int main()
{
    cin >> n >> q;
    for (int x, y, i = 1; i <= n; ++i)
        x = read(), y = read(), p[i] = point(x, y);
    root = build(p, 1, n, 0);
    for (int opt, x, y, i = 1; i <= q; ++i)
    {
        opt = read(), x = read(), y = read();
        if (opt == 1) insert(root, point(x, y), 0);
        else printf("%d\n", query(root, point(x, y)));
    }
    return 0;
}

BZOJ1941 [Sdoi2010]Hide and Seek

同样是一道很裸的题啊!

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

#define N 500005
#define inf 0x3f3f3f3f

int n, dem;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct point
{
    int x, y;
    point() {}
    point(int _x, int _y) : x(_x), y(_y) {}
    bool operator <(const point &p) const
    { return dem ? y < p.y : x < p.x; }
    inline friend int dist(point p1, point p2)
    { return abs(p1.x - p2.x) + abs(p1.y - p2.y); }
} p[N];

struct node
{
    node *son[2];
    point p; int l, r, d, u;

    node() {}
    node(point _p) : p(_p) { l = r = p.x; d = u = p.y; }

    inline void pushup()
    {
        if (son[0])
            l = min(l, son[0]->l), r = max(r, son[0]->r),
            d = min(d, son[0]->d), u = max(u, son[0]->u);
        if (son[1])
            l = min(l, son[1]->l), r = max(r, son[1]->r),
            d = min(d, son[1]->d), u = max(u, son[1]->u);
    }

    int mind(point _p)
    {
        int re = 0;
        if (_p.x < l) re += l - _p.x;
        else if (_p.x > r) re += _p.x - r;
        if (_p.y < d) re += d - _p.y;
        else if (_p.y > u) re += _p.y - u;
        return re;
    }

    int maxd(point _p)
    {
        return max(_p.x - l, r - _p.x) + max(_p.y - d, u - _p.y);
    }
};

node *root;

node *build(point p[], int l, int r, int d)
{
    if (l > r) return NULL;
    int mid = (l + r) >> 1;
    dem = d;
    nth_element(p + l, p + mid, p + r + 1);
    node *re = new node(p[mid]);
    re->son[0] = build(p, l, mid - 1, d ^ 1);
    re->son[1] = build(p, mid + 1, r, d ^ 1);
    re->pushup();
    return re;
}

void insert(node *&pos, point p, int d)
{
    if (!pos) { pos = new node(p); return; }
    dem = d;
    if (p < pos->p) insert(pos->son[0], p, d ^ 1);
    else insert(pos->son[1], p, d ^ 1);
    pos->pushup();
}

int query1(node *pos, point p)
{
    int re = dist(pos->p, p);
    if (re == 0) re = inf;
    int d[2] = {pos->son[0] ? pos->son[0]->mind(p) : inf,
                pos->son[1] ? pos->son[1]->mind(p) : inf};
    int t = d[0] > d[1];
    if (d[t] < re) re = min(re, query1(pos->son[t], p));
    if (d[t ^ 1] < re) re = min(re, query1(pos->son[t ^ 1], p));
    return re;
}

int query2(node *pos, point p)
{
    int re = dist(pos->p, p);
    int d[2] = {pos->son[0] ? pos->son[0]->maxd(p) : -inf,
                pos->son[1] ? pos->son[1]->maxd(p) : -inf};
    int t = d[0] < d[1];
    if (d[t] > re) re = max(re, query2(pos->son[t], p));
    if (d[t ^ 1] > re) re = max(re, query2(pos->son[t ^ 1], p));
    return re;
}

int main()
{
    cin >> n;
    for (int x, y, i = 1; i <= n; ++i)
        x = read(), y = read(), p[i] = point(x, y);
    root = build(p, 1, n, 0);
    int ans = inf;
    for (int i = 1; i <= n; ++i)
        ans = min(ans, query2(root, p[i]) - query1(root, p[i]));
    cout << ans << endl;
    return 0;
}

BZOJ3053 The Closest M Points

这一次做的时候发现这个估价函数很谜啊!

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

#define N 50005
#define sqr(x) ((x) * (x))

int n, k, m, dem;

struct point
{
    int v[5];

    point() {}
    point(int _v[]) { memcpy(v, _v, sizeof v); }

    bool operator <(const point &p) const
    { return v[dem] < p.v[dem]; }

    friend int dist(point &p1, point &p2)
    {
        int re = 0;
        for (int i = 0; i < k; ++i)
            re += sqr(p1.v[i] - p2.v[i]);
        return re;
    }
} p[N];

stack<point> s;

struct node
{
    node *son[2];
    point p;
    node() {}
    node(point _p) : p(_p) {}
};

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

node *root;

node *build(point p[], int l, int r, int d)
{
    if (l > r) return NULL;
    int mid = (l + r) >> 1;
    dem = d;
    nth_element(p + l, p + mid, p + r + 1);
    node *re = new node(p[mid]);
    re->son[0] = build(p, l, mid - 1, (d + 1) % k);
    re->son[1] = build(p, mid + 1, r, (d + 1) % k);
    return re;
}

priority_queue<pair<int, point> > q;

void query(node *pos, point p, int m, int d)
{
    dem = d;
    int t = pos->p < p;
    if (pos->son[t]) query(pos->son[t], p, m, (d + 1) % k);
    q.push(make_pair(dist(pos->p, p), pos->p));
    while ((int)q.size() > m) q.pop();
    if (pos->son[t ^ 1] &&
        ((int)q.size() < m || sqr(p.v[d] - pos->p.v[d]) < q.top().first))
        query(pos->son[t ^ 1], p, m, (d + 1) % k);
}

int main()
{
    while (cin >> n >> k)
    {
        for (int v[5], i = 1; i <= n; ++i)
        {
            for (int j = 0; j < k; ++j)
                v[j] = read();
            p[i] = point(v);
        }
        root = build(p, 1, n, 0);
        int m = read();
        for (int x, v[5], i = 1; i <= m; ++i)
        {
            for (int j = 0; j < k; ++j)
                v[j] = read();
            x = read();
            query(root, point(v), x, 0);
            printf("the closest %d points are:\n", x);
            while (!q.empty())
                s.push(q.top().second), q.pop();
            while (!s.empty())
            {
                for (int j = 0; j < k; ++j)
                    printf("%d%c", s.top().v[j], j == k - 1 ? '\n' : ' ');
                s.pop();
            }
        }
    }
    return 0;
}

BZOJ4066&2683&1176 简单题

这三道题都几乎一模一样,其中后两道不强制在线,可以用 CDQ 分治做。

用 K-D 树维护一个区域内数字的和。然后随便判断判断什么的就好了。

这题如果不重构会 TLE。3000 个插入重构一次好像很科学(跑进了前三)。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
using namespace std;

#define N 200005
#define sqr(x) ((x) * (x))

int n, dem;

struct point
{
    int x, y, val;

    point() {}
    point(int _x, int _y, int _val) : x(_x), y(_y), val(_val) {}

    bool operator <(const point &p) const
    { return dem ? y < p.y : x < p.x; }

    bool check(int _l, int _r, int _d, int _u)
    {
        return x >= _l && x <= _r && y >= _d && y <= _u;
    }
} p[N];

struct node
{
    node *son[2];
    point p;
    int l, r, d, u, sum;

    node() {}
    node (point _p)
    : p(_p), sum(p.val) { l = r = p.x; d = u = p.y; }

    void pushup()
    {
        sum = p.val;
        if (son[0])
            l = min(l, son[0]->l), r = max(r, son[0]->r),
            d = min(d, son[0]->d), u = max(u, son[0]->u), sum += son[0]->sum;
        if (son[1])
            l = min(l, son[1]->l), r = max(r, son[1]->r),
            d = min(d, son[1]->d), u = max(u, son[1]->u), sum += son[1]->sum;
    }

    bool check(int _l, int _r, int _d, int _u)
    { return l >= _l && r <= _r && d >= _d && u <= _u; }

    bool check2(int _l, int _r, int _d, int _u)
    { return r < _l || l > _r || u < _d || d > _u; }

    void *operator new(size_t s);
} nnode[N], *P = nnode;

void *node::operator new(size_t s) { return P++; }

node *root;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

node *build(point p[], int l, int r, int d)
{
    if (l > r) return NULL;
    int mid = (l + r) >> 1;
    dem = d;
    nth_element(p + l, p + mid, p + r + 1);
    node *re = new node(p[mid]);
    re->son[0] = build(p, l, mid - 1, d ^ 1);
    re->son[1] = build(p, mid + 1, r, d ^ 1);
    re->pushup();
    return re;
}

void insert(node *&pos, point p, int d)
{
    if (!pos) { pos = new node(p); return; }
    dem = d;
    if (p < pos->p) insert(pos->son[0], p, d ^ 1);
    else insert(pos->son[1], p, d ^ 1);
    pos->pushup();
}

int query(node *pos, int l, int r, int d, int u)
{
    if (!pos) return 0;
    if (pos->check(l, r, d, u)) return pos->sum;
    int re = 0;
    if (pos->p.check(l, r, d, u)) re += pos->p.val;
    if (pos->son[0] && !pos->son[0]->check2(l, r, d, u))
        re += query(pos->son[0], l, r, d, u);
    if (pos->son[1] && !pos->son[1]->check2(l, r, d, u))
        re += query(pos->son[1], l, r, d, u);
    return re;
}

int main()
{
    read();
    int opt, ans = 0;
    while ((opt = read()) != 3)
    {
        if (opt == 1)
        {
            int x = read() ^ ans, y = read() ^ ans, z = read() ^ ans;
            p[++n] = point(x, y, z);
            if (n % 3000 == 0) P = nnode, root = build(p, 1, n, 0);
            else insert(root, point(x, y, z), 0);
        }
        if (opt == 2)
        {
            int l = read() ^ ans, d = read() ^ ans,
                r = read() ^ ans, u = read() ^ ans;
            printf("%d\n", ans = query(root, l, r, d, u));
        }
    }
    return 0;
}