Luogu P3769 [CH弱省胡策R2]TATT

题目描述

https://www.luogu.com.cn/problem/P3769

简要题意：给定 $n$ 个思维空间中的点，求一条最长的路径，满足任意一维坐标都是单调不降的

$n\le 5\times 10^4$

Solution

大概就是一个四维偏序

我们考虑 $cdq$ 套 $cdq$，在内层 $cdq$ 中用树状数组解决二维偏序

由于计算的是 $dp$ 值，要注意计算贡献和 $cdq$ 的顺序

至于 $cdq$ 内如何套 $cdq$，大概就是记录一下这个数是左边还是右边的

时间复杂度 $O(n\log^3 n)$，常数很小

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <tuple>
#include <cstring>
#include <vector>
#define maxn 50010
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m;

struct node {
    int x, y, z, w, id, v;
} a[maxn], t1[maxn], t2[maxn];

int b[maxn], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i].w;
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i].w = lower_bound(b + 1, b + cnt + 1, a[i].w) - b;
}

int Bit[maxn];
void add(int i, int v) { while (i <= cnt) Bit[i] = max(Bit[i], v), i += lowbit(i); }

void clear(int i) { while (i <= cnt) Bit[i] = 0, i += lowbit(i); } 

int query(int i) {
    int s = 0;
    while (i) s = max(s, Bit[i]), i -= lowbit(i);
    return s; 
}

int f[maxn]; 
void Cdq(node *a, int l, int r) {
    if (l == r) return ; int m = l + r >> 1, j = l - 1; 
    Cdq(a, l, m);
    memcpy(t2 + l, a + l, sizeof (node) * (r - l + 1));
    sort(t2 + l, t2 + m + 1, [](const node &u, const node &v) { return u.z < v.z; });
    sort(t2 + m + 1, t2 + r + 1, [](const node &u, const node &v) { return u.z < v.z; });
    for (int i = m + 1; i <= r; ++i) {
        if (!t2[i].v) continue;
        while (j < m && t2[j + 1].z <= t2[i].z) {
            ++j; if (t2[j].v) continue;
            add(t2[j].w, f[t2[j].id]);
        }
        f[t2[i].id] = max(f[t2[i].id], query(t2[i].w) + 1); 
    }
    for (int i = l; i <= j; ++i) clear(t2[i].w); 
    Cdq(a, m + 1, r);
}

void cdq(node *a, int l, int r) {
    if (l == r) return ; int m = l + r >> 1;
    cdq(a, l, m);
    memcpy(t1 + l, a + l, sizeof (node) * (r - l + 1)); 
    for (int i = l; i <= m; ++i) t1[i].v = 0;
    for (int i = m + 1; i <= r; ++i) t1[i].v = 1;
    auto cmp = [](const node &u, const node &v) {
        //return make_tuple(u.y, u.z, u.w) < make_tuple(v.y, v.z, v.w);
        return u.y < v.y;
    };
    stable_sort(t1 + l, t1 + r + 1, cmp);
    Cdq(t1, l, r); cdq(a, m + 1, r);
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; fill(f + 1, f + n + 1, 1); 
    for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[i].z >> a[i].w, a[i].id = i;
    init_hash(); 
    auto cmp = [](const node &u, const node &v) {
        return make_tuple(u.x, u.y, u.z, u.w) < make_tuple(v.x, v.y, v.z, v.w);
    };
    sort(a + 1, a + n + 1, cmp); cdq(a, 1, n);
    cout << *max_element(f + 1, f + n + 1) << "\n";
    return 0;
}