题意

求带权四维最长不下降子序列的长度。

$1 \le n \le 5 \times 10^4$。

分析

这里给一个单层 cdq 分治加上树套树的做法。时间复杂度 $O(n\log^3n)$。

如果是三维的话，就是 P2487 [SDOI2011] 拦截导弹，可以用 cdq 分治加上树状数组解决。

考虑三维的时候，我们用分治处理了一维，用排序加双指针处理了一维，用树状数组处理了最后一维。现在有多了一维，很多题解用的是再套一层 cdq 分治，但是我一直写挂。

考虑最后一维实际上可以再用一个数据结构来处理，比如树套树。我写的是树状数组套线段树，这样子单层是 $O(n\log^2n)$ 的，可以单点修改，查询二维偏序最大值。然后外面用 cdq 分治，时间复杂度 $O(n\log^3n)$。

我是觉得不难写，因为求最大值没用初始化负无穷 WA 了一次。注意要离散化。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define il inline
#define N 100005
il int rd(){
    int s = 0, w = 1;
    char ch = getchar();
    for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
    for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
    return s * w;
}
int n, f[N], nls[N], cnt, maxn = -1e18;
struct Point{
    int a, b, c, d, k, id;
}p[N];
il bool cmp1(Point x, Point y){return x.a != y.a ? x.a < y.a : x.b != y.b ? x.b < y.b : x.c != y.c ? x.c < y.c : x.d != y.d ? x.d < y.d : x.id < y.id;}
il bool cmp2(Point x, Point y){return x.b != y.b ? x.b < y.b : x.a != y.a ? x.a < y.a : x.c != y.c ? x.c < y.c : x.d != y.d ? x.d < y.d : x.id < y.id;}
int rt[N], tr[N << 6], ls[N << 6], rs[N << 6], ep;
void upd(int &p, int l, int r, int x, int k){
    if (!p) p = ++ep, tr[p] = ls[p] = rs[p] = 0;
    if (l == r) return tr[p] = max(tr[p], k), void(0);
    int mid = (l + r) >> 1;
    if (x <= mid) upd(ls[p], l, mid, x, k); else upd(rs[p], mid + 1, r, x, k);
    tr[p] = max(tr[ls[p]], tr[rs[p]]);
}
int qry(int p, int l, int r, int nl, int nr){
    if (!p) return 0;
    if (nl <= l && r <= nr) return tr[p];
    int mid = (l + r) >> 1, ans = 0;
    if (nl <= mid) ans = max(ans, qry(ls[p], l, mid, nl, nr)); if (nr > mid) ans = max(ans, qry(rs[p], mid + 1, r, nl, nr));
    return ans;
}
il void add(int x, int y, int k){for (int i = x; i <= n; i += (i & (-i))) upd(rt[i], 1, n, y, k);}
il int ask(int x, int y){int ans = 0;for (int i = x; i >= 1; i -= (i & (-i))) ans = max(ans, qry(rt[i], 1, n, 1, y));return ans;}
il void clr(int x){for (int i = x; i <= n; i += (i & (-i))) rt[i] = 0;}
void cdq(int l, int r){
    if (l == r) return ;
    sort (p + l, p + r + 1, cmp1);
    int mid = (l + r) >> 1;
    cdq(l, mid);
    sort (p + l, p + mid + 1, cmp2), sort (p + mid + 1, p + r + 1, cmp2);
    for (int i = l, j = mid + 1; j <= r; j++){
        for (; i <= mid && p[i].b <= p[j].b; i++) add(p[i].c, p[i].d, f[p[i].id]);
        f[p[j].id] = max(f[p[j].id], ask(p[j].c, p[j].d) + p[j].k);
    }
    for (int i = l; i <= mid; i++) clr(p[i].c);
    ep = 0;
    cdq(mid + 1, r);
}
signed main(){
    n = rd();
    for (int i = 1; i <= n; i++) p[i] = Point{rd(), rd(), rd(), rd(), rd(), i}, f[i] = p[i].k;
    for (int i = 1; i <= n; i++) nls[i] = p[i].a;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].a = lower_bound(nls + 1, nls + cnt + 1, p[i].a) - nls;
    for (int i = 1; i <= n; i++) nls[i] = p[i].b;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].b = lower_bound(nls + 1, nls + cnt + 1, p[i].b) - nls;
    for (int i = 1; i <= n; i++) nls[i] = p[i].c;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].c = lower_bound(nls + 1, nls + cnt + 1, p[i].c) - nls;
    for (int i = 1; i <= n; i++) nls[i] = p[i].d;sort (nls + 1, nls + n + 1), cnt = unique(nls + 1, nls + n + 1) - nls - 1;
    for (int i = 1; i <= n; i++) p[i].d = lower_bound(nls + 1, nls + cnt + 1, p[i].d) - nls;
    cdq(1, n);
    for (int i = 1; i <= n; i++) maxn = max(maxn, f[i]);
    printf ("%lld\n", maxn);
    return 0;
}