P5621 [DBOI2019] 德丽莎世界第一可爱 /【模板】四维偏序 题解

· · 题解

Solve

考虑从常规的三维偏序扩展为四维偏序。

同样地，我们先按第一维 a 排序。

我们对第二维 b CDQ 分治，记 \operatorname{cdqB}(l,r) 表示处理所有 [l,r] 之间的偏序转移关系，记 \text{mid}=\dfrac{l+r}{2}。

同样地，我们递归 \operatorname{cdqB}(l,\text{mid}) 和 \operatorname{cdqB}(\text{mid}+1,r)，再两次递归中间处理跨越 \text{mid} 的转移。

我们把 [l,\text{mid}] 中的元素打上黑色标记，把 [\text{mid}+1,r] 中的元素打上白色标记，把 [l,r] 中的元素按照第三维 c 排序。

我们再对 c CDQ，记 \operatorname{cdqC}(l,r) 表示处理所有 [l,r] 之间 c,d 的偏序转移关系，这就是普通的三维偏序了。

我们只需要考虑所有黑色点对白色点的贡献。可以把黑色点看做修改操作，白色点为询问操作。

同样可以把其扩展到 k 维偏序，时间复杂度 \mathcal{O}(n\log^{k-1}n)。

注意使用 stable_sort！！！！

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sort stable_sort
#define pii pair<int, int> 
#define fi first
#define se second 
#define mp make_pair
int n, f[200010];
int len, lsh[200010];
struct Node {
    int id, bp, a, b, c, d, w;
} a[50010], b[50010], c[50010]; 
bool cmpD(Node a, Node b) { return a.d < b.d; }
bool cmpC(Node a, Node b) {
    if (a.c != b.c) return a.c < b.c; else return cmpD(a, b);
}
bool cmpB(Node a, Node b) {
    if (a.b != b.b) return a.b < b.b; else return cmpC(a, b);
}
bool cmpA(Node a, Node b) {
    if (a.a != b.a) return a.a < b.a; else return cmpB(a, b);
}
struct Bit {
    int w[200010];
    void add(int p, int x) {
        for (int i = p; i <= len; i += i & (-i)) w[i] = max(w[i], x);
    }
    void put(int p) {
        for (int i = p; i <= len; i += i & (-i)) w[i] = 0;
    }
    int query(int p) {
        int res = 0;
        for (int i = p; i; i -= i & (-i)) res = max(res, w[i]);
        return res;
    }
} bit;
void cdqC(int l, int r, Node *a) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    cdqC(l, mid, a);
    for (int i = l; i <= r; i++) c[i] = a[i];
    sort(c + l, c + mid + 1, cmpC); sort(c + mid + 1, c + r + 1, cmpC);
    int lp = l - 1;
    for (int i = mid + 1; i <= r; i++) {
        while (lp < mid && c[lp + 1].c <= c[i].c) {
            lp++;
            if (c[lp].bp) bit.add(c[lp].d, f[c[lp].id]);
        }
        if (c[i].bp == 0) f[c[i].id] = max(f[c[i].id], bit.query(c[i].d));
    }
    lp = l - 1;
    for (int i = mid + 1; i <= r; i++) {
        while (lp < mid && c[lp + 1].c <= c[i].c) {
            lp++;
            bit.put(c[lp].d);
        }
    }
    cdqC(mid + 1, r, a);
}
void cdqB(int l, int r) {
    if (l == r) {
        f[a[l].id] += a[l].w;
        return;
    }
    int mid = (l + r) >> 1;
    cdqB(l, mid);
    for (int i = l; i <= mid; i++) a[i].bp = 1;
    for (int i = mid + 1; i <= r; i++) a[i].bp = 0;
    for (int i = l; i <= r; i++) b[i] = a[i];
    sort(b + l, b + r + 1, cmpB); cdqC(l, r, b);
    cdqB(mid + 1, r);
}
void plsh(int x) { lsh[++len] = x; }
void lb(int &x) { x = lower_bound(lsh + 1, lsh + len + 1, x) - lsh; }
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        a[i].id = i;
        cin >> a[i].a >> a[i].b >> a[i].c >> a[i].d >> a[i].w;
        plsh(a[i].a), plsh(a[i].b), plsh(a[i].c), plsh(a[i].d);
    }
    sort(lsh + 1, lsh + len + 1); 
    len = unique(lsh + 1, lsh + len + 1) - lsh - 1;
    for (int i = 1; i <= n; i++) lb(a[i].a), lb(a[i].b), lb(a[i].c), lb(a[i].d);
    sort(a + 1, a + n + 1, cmpA);
    cdqB(1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, f[i]);
    cout << ans << endl;
    return 0;
}