P3769 [CH弱省胡策R2]TATT(KD-Tree)

做kd-tree题找到了这道题 顺便推销blog

---

这题是四维意义下的最长上升子序列, 但如果将第一维排序就变成三维问题了, kd-tree时间复杂度应该会更优

总而言之就是
\[ \large{dp_i = \max_{x_j\le x_i,y_j\le y_i,z_j \le z_i} dp_j + 1} \]
从前向后扫, 找到三维都比它小的dp值最大的点, 找点可以用kd-tree来优化

可以采用一下技巧和剪枝:

• 如果当前子树dp最大值小于等于当前已搜出的最优答案直接返回即可肯定不会更新了
• 如果当前子树的点都在范围内, 直接拿最大值更新答案返回
• 如果当前子树有一维的最小值超过了范围, 那么代表着这个子树中无一满足条件, 直接返回即可
• 每次插入不用替罪羊思想重构, 可以直接提前把树建出来, 初始dp值都设为零, 加入操作相当于激活一个点, 具体就是像线段树那样从上向下搜到那个点, 返回时一路更新就行了

有了以上剪枝, 足够通过此题

这里有一些数据可能对你有用 可以修改url找到其他数据 从18998到19003

#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 ("hs.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;
}