P5621 [DBOI2019]德丽莎世界第一可爱

· · 题解

P5621 [DBOI2019]德丽莎世界第一可爱 本题最优解

题目传送门

前置知识：带修 \text{K-D Tree}。

用的不是 \text{CDQ}，不是八叉树，是 \text{K-D Tree}。

本题主要讲解的不是带修 \text{K-D Tree} 优化 \text{dp} 的思路，而是如何优化到可以通过甚至最优解。

我们发现这是一个典型的四维偏序问题，我们一次将一二三四维排序后，就可以 \text{dp}。实际上 \text{dp} 的过程就是求一个 3 维长方体内点权最大值问题，这个东西可以用 \text{K-D Tree} 维护。

我们先把一个带修 \text{K-D Tree} 的代码写出来，您可能可以获得 60-100 的各种分数，现在，我们就开始优化。

优化 1，结构体存储：这一点想必卡过常的都知道。

优化 2，把数据中所有 \text{collapse} \leq 0 的值更新最大值，然后直接去掉，因为这种打了白打的可以直接去掉。

优化 3，这个优化非常重要，就是实际上 \text{K-D Tree} 查询是一个剪枝搜索的过程，我们在一般的矩形包含关系外增加一个最优化箭枝，具体来说，就是用一个全局变量记录搜索过程的最大值，如果现在搜索的一整棵子树最大值都不超过之前搜到的最大值，可以直接跳过。

优化 4，这个优化类似于一个小贪心。你 \text{K-D Tree} 查询时，不是要递归左右孩子吗。然后你就优先递归其子树最大值更大的子树，然后再递归较小的，这个东西是要配着优化 3 用的。

优化 5，递归过程中少传参数，尽量开全局变量。

优化 6，我们发现 \text{K-D Tree} 重构系数在 0.72 左右最优秀。

加上这些优化，您就可以享受从 \text{TLE} 到吊打其它做法的快感！。

最后，如果对有些优化不清楚，可以参考代码。

\text{Code:} 
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline T sqr(T x) { return x * x; }
#define lc(x) w[x].l
#define rc(x) w[x].r
const int N = 2e5 + 10;
const double alpha = 0.715;
const int SIZ = 1 << 14;
inline char getc() {
    static char bf[SIZ], *begin = bf, *end = bf;
    if (begin == end) begin = bf, end = bf + fread(bf, 1, SIZ, stdin);
    if (begin == end) return EOF;
    return *begin++;
}
inline int read() {
    static char tmp;
    static int ans, flag;
    tmp = getc(), flag = 1, ans = 0;
    while (!isdigit(tmp)) {
        if (tmp == '-') flag = -1;
        tmp = getc();
    }
    while (isdigit(tmp)) ans = (ans << 1) + (ans << 3) + (tmp ^ 48), tmp = getc();
    return ans * flag;
}
int n, rt, cur, g[N], tot;
struct KDTNode {
    int x, y, z;
    long long v;
    int siz, l, r, L, R, D, U, F, B, d;
    long long sum;
} w[N];
inline long long max(long long a, long long b, long long c) { return max(a, max(b, c)); }
inline void pushup(int u) {
    int ls = lc(u), rs = rc(u);
    w[u].siz = w[ls].siz + w[rs].siz + 1;
    w[u].sum = max(w[ls].sum, w[rs].sum, w[u].v);
    w[u].L = w[u].R = w[u].x;
    w[u].U = w[u].D = w[u].y;
    w[u].B = w[u].F = w[u].z;
    if (lc(u)) {
        w[u].L = min(w[u].L, w[ls].L), w[u].R = max(w[u].R, w[ls].R);
        w[u].D = min(w[u].D, w[ls].D), w[u].U = max(w[u].U, w[ls].U);
        w[u].B = min(w[u].B, w[ls].B), w[u].F = max(w[u].F, w[ls].F);
    }
    if (rc(u)) {
        w[u].L = min(w[u].L, w[rs].L), w[u].R = max(w[u].R, w[rs].R);
        w[u].D = min(w[u].D, w[rs].D), w[u].U = max(w[u].U, w[rs].U);
        w[u].B = min(w[u].B, w[rs].B), w[u].F = max(w[u].F, w[rs].F);
    }
}
inline bool canrebuild(int u) { return alpha * w[u].siz <= (double)max(w[lc(u)].siz, w[rc(u)].siz); }
inline bool cmp1(int x, int y) { return w[x].x < w[y].x; }
inline bool cmp2(int x, int y) { return w[x].y < w[y].y; }
inline bool cmp3(int x, int y) { return w[x].z < w[y].z; }
int build(int l, int r) {
    if (l > r) return 0;
    int mid = l + r >> 1;
    double av1 = 0, av2 = 0, av3 = 0, va1 = 0, va2 = 0, va3 = 0;
    for (int i = l; i <= r; i++) av1 += w[g[i]].x, av2 += w[g[i]].y, av3 += w[g[i]].z;
    av1 /= r - l + 1;
    av2 /= r - l + 1;
    av3 /= r - l + 1;
    for (int i = l; i <= r; i++)
        va1 += sqr(w[g[i]].x - av1), va2 += sqr(w[g[i]].y - av2), va3 += sqr(w[g[i]].z - av3);
    if (va1 > va2 && va1 > va3)
        nth_element(g + l, g + mid, g + r + 1, cmp1), w[g[mid]].d = 1;
    else if (va2 > va3)
        nth_element(g + l, g + mid, g + r + 1, cmp2), w[g[mid]].d = 2;
    else
        nth_element(g + l, g + mid, g + r + 1, cmp3), w[g[mid]].d = 3;
    lc(g[mid]) = build(l, mid - 1), rc(g[mid]) = build(mid + 1, r);
    pushup(g[mid]);
    return g[mid];
}
void dfs(int u) {
    if (!u) return;
    dfs(lc(u));
    g[++tot] = u;
    dfs(rc(u));
}
inline void rebuild(int &u) {
    tot = 0;
    dfs(u);
    u = build(1, tot);
}
int needpush;
void insert(int &u) {
    if (!u) {
        u = needpush, w[u].d = 2;
        pushup(u);
        return;
    }
    if (w[u].d == 1) {
        if (w[needpush].x <= w[u].x)
            insert(lc(u));
        else
            insert(rc(u));
    } else if (w[u].d == 2) {
        if (w[needpush].y <= w[u].y)
            insert(lc(u));
        else
            insert(rc(u));
    } else {
        if (w[needpush].z <= w[u].z)
            insert(lc(u));
        else
            insert(rc(u));
    }
    pushup(u);
    if (canrebuild(u)) rebuild(u);
}
int xl, xr, yl, yr, zl, zr;
long long nowans;
void query(int u) {
    if (nowans >= w[u].sum) return;
    if (!u || xr < w[u].L || yr < w[u].D || zr < w[u].B) return;
    if (w[u].R <= xr && w[u].U <= yr && w[u].F <= zr) {
        nowans = max(nowans, w[u].sum);
        return;
    }
    if (w[u].x <= xr && w[u].y <= yr && w[u].z <= zr) nowans = max(nowans, w[u].v);
    if (w[lc(u)].sum > w[rc(u)].sum)
        query(lc(u)), query(rc(u));
    else
        query(rc(u)), query(lc(u));
}
const int P = 1e8 + 10;
struct Node {
    int x, y, z, k;
    long long w;
    inline void gread() { x = read(), y = read(), z = read(), k = read(), w = read(), x += P, y += P, z += P, k += P; }
    inline bool operator<(const Node &b) const { return x != b.x ? x < b.x : (y != b.y ? y < b.y : (z != b.z ? z < b.z : k < b.k)); }
} a[N], ga[N];
long long f[N];
int main() {
    cin >> n;
    int cnt = 0;
    long long maxn = -0x3f3f3f3f3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        a[i].gread();
        if (a[i].w <= 0)
            maxn = max(maxn, a[i].w);
        else
            ga[++cnt] = a[i];
    }
    n = cnt;
    sort(ga + 1, ga + cnt + 1);
    for (int i = 1; i <= n; i++) {
        xl = 1, xr = ga[i].y, yl = 1, yr = ga[i].z, zl = 1, zr = ga[i].k;
        nowans = 0, query(rt);
        maxn = max(maxn, f[i] = ga[i].w + nowans);
        w[++cur] = {ga[i].y, ga[i].z, ga[i].k, f[i]};
        needpush = cur, insert(rt);
    }
    cout << maxn;
    return 0;
}