zcmimi's blog
查看原题

点击跳转

k-d tree模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define I inline
#define ll long long
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

const int N = 200500;
struct node {
    int d[4];
    bool operator < (const node &k) const {
        for (int i = 0;i < 4; i++) 
            if (d[i] != k.d[i]) return d[i] < k.d[i];
        return 0;
    }
}p[N];

int g[N], k;

I bool cmp(int a, int b) {
    return p[a].d[k] < p[b].d[k];
}

#define ls son[x][0]
#define rs son[x][1]

int son[N][2];
int mx[N][3], mn[N][3], mxa[N], res[N], ans;
I void Mn(int &x, int y) { if (x > y) x = y; }
I void Mx(int &x, int y) { if (x < y) x = y; }

I void maintain(int x) {
    for (int i = 0;i <= 2; i++) {
        mx[x][i] = mn[x][i] = p[x].d[i+1];
        if (ls) Mx(mx[x][i], mx[ls][i]), Mn(mn[x][i], mn[ls][i]);
        if (rs) Mx(mx[x][i], mx[rs][i]), Mn(mn[x][i], mn[rs][i]);
    }
}
int build(int l, int r, int d) {
    if (l > r) return 0;
    int mid = (l + r) >> 1;
    k = d + 1, nth_element(g + l, g + mid, g + r + 1, cmp);
    son[g[mid]][0] = build(l, mid - 1, (d + 1) % 3);
    son[g[mid]][1] = build(mid + 1, r, (d + 1) % 3);
    maintain(g[mid]); return g[mid];
}

int tmp;

// 判断x点是否在y点范围以内 
inline bool in(int *x, int *y) {
    int cnt = 0;
    for (int i = 0;i < 3; i++) cnt += (x[i] <= y[i]);
    return cnt == 3;
}

void query(int x, int y) {
    if (mxa[x] <= tmp) return;
    if (!in(mn[x], p[y].d + 1)) return;
    if (in(mx[x], p[y].d + 1)) return tmp = mxa[x], void();
    if (in(p[x].d + 1, p[y].d + 1)) Mx(tmp, res[x]);
    if (ls) query(ls, y); if (rs) query(rs, y);
}

// 激活操作 
void upit(int x, int y) {
    if (x == y) {
        res[x] = tmp, Mx(mxa[x], res[x]); return;
    }
    if (!in(p[y].d + 1, mx[x]) || !in(mn[x], p[y].d + 1)) return;
    // 如果y点不在里面就返回 
    if (ls) upit(ls, y); if (rs) upit(rs, y);
    Mx(mxa[x], mxa[ls]), Mx(mxa[x], mxa[rs]);
}

int rt, n;
int main() {
    freopen ("../in.in","r",stdin);
    read(n);
    for (int i = 1;i <= n; i++) {
        read(p[i].d[0]), read(p[i].d[1]);
        read(p[i].d[2]), read(p[i].d[3]);
        g[i] = i;
    }
    sort(p + 1, p + n + 1); rt = build(1, n, 0);
    for (int i = 1;i <= n; i++) 
        tmp = 0, query(rt, i), tmp++, upit(rt, i), Mx(ans, tmp);
    cout << ans << endl;
    return 0;
}
LG 4148 简单题
comment评论
Search
search