Catshao

用户名：Catshao

访问量：28829

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

人类智慧分块
浏览：186

你可能喜欢

四维偏序（原题：[DBOI2019]德丽莎世界第一可爱）

　　作者: Catshao　　　　发表时间：2022-02-23 09:20:13 浏览：252　|　评论：0　

原题链接：四维偏序

反正也没人整优质题解了，Latex炸了就炸了吧。[更好的阅读体验](https://cat-shao.blog.luogu.org/solution-p5621)

提供一个跑得比较快的八叉树解法。

### 二维线段树

本题二维线段树不一定能过去，我在这里放一下只是想做一下对比。会的大佬可以直接跳过。

以我目前的认知四叉树 $\ne$ 二维线段树。

![二维线段树。数字表示当前结点是父结点的第几个子结点](https://cdn.luogu.com.cn/upload/image_hosting/vhs5mt4s.png)

类似于线段树，二维线段树维护的是一个矩形。对于每一个结点都对应一块矩形区域，将其从中心分成四个子结点，直到区域大小为 $1 \times 1$ 不可再分。根结点的矩形区域对应整个平面。矩形修改类似线段树的区间修改，矩形查询类似线段树的区间查询。树高是 $O(\max(\log n, \log m))$ 的其中 $n, m$ 表示我们维护的平面是 $n \times m$ 的，因此单点修改单点查询都是 $O(\max(\log n, \log m))$ 的，矩形修改矩形查询是 $O(\log n \log m)$ 的。

如果将所有结点都存下来，空间复杂度是 $O(n^2)$ 的显然不能承受，我们可以使用动态开点线段树的思路，用到哪就开到哪。对于单点修改（插入），会新建 $O(\max(\log n, \log m))$ 个结点，对于矩形修改，会新建 $O(\log n \log m)$ 个结点。

时间复杂度：单点询问/修改 $O(\max(\log n, \log m))$ ，矩形询问/修改 $O(\log n \log m)$ 。

优点：相比于树套树较为好写，支持矩形修改。

缺点：空间复杂度跟单点修改和矩形修改有直接关系，有 $k, l$ 次单点修改和矩形修改的空间复杂度为 $O(k \max(\log n, \log m) + l \log n \log m)$ ，容易被卡空间。遍历一个矩形区域内所有结点不是线性的，而是结点个数 $\times$ 树高，相比之下 K-D Tree 可以做到线性。

### 四叉树

八叉树就是三维的四叉树，因此我们先来讲四叉树。

四叉树是一种空间索引树，每个结点都对应一块矩形区域。现在 $n \times m$ 的平面上共有 $k$ 个点。根结点的矩形区域对应整个平面。如果当前结点对应区域包含两个以上的点，那么将当前结点的区域从中心一分为四变成当前结点的四个子结点，每个子结点再继续划分，直到一个叶结点内只包含一个点。

![](https://cdn.luogu.com.cn/upload/image_hosting/rpd02uf3.png)

![](https://cdn.luogu.com.cn/upload/image_hosting/8jfr532j.png)

不同于二维线段树，四叉树内的点坐标可以是小数。在存储整数坐标的点时，最坏时间复杂度同二维线段树，更多情况下树高低于二维线段树，跑得比二维线段树更快。

优点：效率高，空间占用少，枚举矩形区域内每一个点时线性的。

缺点：不支持矩形修改。

### 八叉树

![](https://cdn.luogu.com.cn/upload/image_hosting/znik06w8.png)

其实就是二维变三维，四个叉变成八个叉，其他没变。

### 本题

简化题意：给定 $n$ 个点 $\{(x_n, y_n, z_n, w_n, c_n)\}$ ，求出一条价值最大的路径并且这条路径的每一个点的 $x_i, y_i, z_i, w_i$ 相比于前一个点都不降。一条路径的价值为这条路径上点的 $c$ 的和。

将这些点按 $\{x_n\}$ 升序排序。这样最长路径变为最长子序列（即前后顺序不能换）。定义 $dp_i$ 为子序列最后一项在 $i$ 的最大价值，则有状态转移方程：

$${\large dp_i = \max\left\{\max_{j < i \wedge  y_j \le y_i \wedge z_j \le z_i \wedge w_j\le w_i}\{dp_j\}, 0 \right\} + c_i} $$

考虑到这是一个四维偏序，可以用八叉树解决。

从 1 至 $n$ 扫，维护一个八叉树。扫到 $i$ 时求 $dp_i$ ，也就是询问八叉树中从 $(1, 1, 1)$ 到 $(y_i, z_i, w_i)$ 的长方体内点权最大的点（还得跟 0 取最大），然后将一个坐标为 $(y_i, z_i, w_i)$ 点权为 $dp_i$ 的点加入到八叉树中。

由于本题没给出 $y, z, w$ 的范围，八叉树的效率跟这些范围有直接关系，因此我们需要离散化。分别将所有点的 $y, z, w$ 离散化，这样不仅确定了范围还提高了效率。

-------

到这为止，直接写一个八叉树，然后你会发现你 TLE 了。由于我们求的是最大值因此可以在查询的时候剪枝，如果当前区域的最大值小于已有最大值，直接放弃这一区域的查找。

我写的八叉树大常数，开 O2 后跑得比较快。

```cpp
//
// Created by Cat-shao on 2022/2/22.
//

#include <bits/stdc++.h>
using namespace std;

namespace oct {
    const int MAX_POOL = 8e5;
    const int MAX_N = 5e4 + 5;
    typedef tuple<int, int, int> point;

class node {
    public:
        long long maxi;
        node *ch[8];
        point *v;
    };

node memPool[MAX_POOL];
    node *memTop;
    node *nil;
    point pointPool[MAX_N];
    point *pointTop;
    point *none;

node *newNode(point *point) {
        node *cur = memTop++;
        cur->maxi = 0;
        cur->v = point;
        fill(cur->ch, cur->ch + 8, nil);
        return cur;
    }

point *newPoint(int x, int y, int z) {
        point *p = pointTop++;
        *p = point(x, y, z);
        return p;
    }

class init {
    public:
        init() {
            pointTop = pointPool;
            none = newPoint(0, 0, 0);
            memTop = memPool;
            nil = newNode(none);
            nil->maxi = 0;
            fill(nil->ch, nil->ch + 8, nil);
        }
    } bminit;

class oct {
    public:
        node *root;
        int maxx, maxy, maxz;

oct(int _maxx, int _maxy, int _maxz) {
            maxx = _maxx + 1;
            maxy = _maxy + 1;
            maxz = _maxz + 1;
            root = nil;
        }

int getType(int xl, int xr, int yl, int yr, int zl, int zr, point *p) {
            return (get<0>(*p) >= (xl + xr) >> 1) + ((get<1>(*p) >= (yl + yr) >> 1) << 1) + ((get<2>(*p) >= (zl + zr) >> 1) << 2);
        }

void move(int &xl, int &xr, int &yl, int &yr, int &zl, int &zr, int type) {
            if (type & 1) {
                xl = (xl + xr) >> 1;
            } else {
                xr = (xl + xr) >> 1;
            }
            if ((type >> 1) & 1) {
                yl = (yl + yr) >> 1;
            } else {
                yr = (yl + yr) >> 1;
            }
            if ((type >> 2) & 1) {
                zl = (zl + zr) >> 1;
            } else {
                zr = (zl + zr) >> 1;
            }
        }

void add(point *p, long long v) {
            if (root == nil) {
                root = newNode(p);
                root->maxi = v;
                return;
            }
            node *cur = root;
            int xl = 1, xr = maxx, yl = 1, yr = maxy, zl = 1, zr = maxz;
            for (;;) {
                if (*cur->v == *p) {
                    cur->maxi = max(cur->maxi, v);
                    break;
                }
                int temp = getType(xl, xr, yl, yr, zl, zr, cur->v);
                if (cur->v != none) { // 只有叶结点才能存储点
                    cur->ch[temp] = newNode(cur->v);
                    cur->ch[temp]->maxi = cur->maxi;
                    cur->v = none;
                }
                cur->maxi = max(cur->maxi, v);
                temp = getType(xl, xr, yl, yr, zl, zr, p);
                if (cur->ch[temp] == nil) {
                    cur->ch[temp] = newNode(p);
                    cur->ch[temp]->maxi = v;
                    break;
                } else {
                    move(xl, xr, yl, yr, zl, zr, temp);
                    cur = cur->ch[temp];
                }
            }
        }

long long query(int x, int y, int z) {
            long long res = 0; // x, y, z 没有加一仍是闭区间
            function<void(node *, int, int, int, int, int, int)> dfs;
            dfs = [&](node *cur, int xl, int xr, int yl, int yr, int zl, int zr) {
                if (cur == nil || xl > x || yl > y || zl > z || res >= cur->maxi) {
                    return;
                } else if (xr - 1 <= x && yr - 1 <= y && zr - 1 <= z) {
                    res = max(res, cur->maxi);
                } else if (cur->v != none) {
                    res = max(res, (get<0>(*cur->v) <= x) && (get<1>(*cur->v) <= y) && (get<2>(*cur->v) <= z) ? cur->maxi : 0);
                } else {
                    int xmid = (xl + xr) >> 1, ymid = (yl + yr) >> 1, zmid = (zl + zr) >> 1;
                    dfs(cur->ch[0], xl, xmid, yl, ymid, zl, zmid);
                    dfs(cur->ch[1], xmid, xr, yl, ymid, zl, zmid);
                    dfs(cur->ch[2], xl, xmid, ymid, yr, zl, zmid);
                    dfs(cur->ch[3], xmid, xr, ymid, yr, zl, zmid);
                    dfs(cur->ch[4], xl, xmid, yl, ymid, zmid, zr);
                    dfs(cur->ch[5], xmid, xr, yl, ymid, zmid, zr);
                    dfs(cur->ch[6], xl, xmid, ymid, yr, zmid, zr);
                    dfs(cur->ch[7], xmid, xr, ymid, yr, zmid, zr);
                }
            };
            dfs(root, 1, maxx, 1, maxy, 1, maxz);
            return res;
        }
    };
}

const int MAX_N = 5e4 + 5;
typedef tuple<int, int, int, int, long long> TII;

int n;
TII a[MAX_N];
int hy[MAX_N], hz[MAX_N], hw[MAX_N], ky, kz, kw;
long long dp[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> get<0>(a[i]) >> get<1>(a[i]) >> get<2>(a[i]) >> get<3>(a[i]) >> get<4>(a[i]);
        hy[i] = get<1>(a[i]);
        hz[i] = get<2>(a[i]);
        hw[i] = get<3>(a[i]);
    }
    sort(hy + 1, hy + n + 1);
    sort(hz + 1, hz + n + 1);
    sort(hw + 1, hw + n + 1);
    ky = unique(hy + 1, hy + n + 1) - (hy + 1);
    kz = unique(hz + 1, hz + n + 1) - (hz + 1);
    kw = unique(hw + 1, hw + n + 1) - (hw + 1);
    for (int i = 1; i <= n; ++i) {
        get<1>(a[i]) = lower_bound(hy + 1, hy + ky + 1, get<1>(a[i])) - hy;
        get<2>(a[i]) = lower_bound(hz + 1, hz + kz + 1, get<2>(a[i])) - hz;
        get<3>(a[i]) = lower_bound(hw + 1, hw + kw + 1, get<3>(a[i])) - hw;
    }
    sort(a + 1, a + n + 1);
    oct::oct tree(ky, kz, kw);
    for (int i = 1; i <= n; ++i) {
        dp[i] = max(tree.query(get<1>(a[i]), get<2>(a[i]), get<3>(a[i])), 0ll) + get<4>(a[i]);
        tree.add(oct::newPoint(get<1>(a[i]), get<2>(a[i]), get<3>(a[i])), dp[i]);
    }
    cout << *max_element(dp + 1, dp + n + 1) << endl;
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

宏定义

IP判断（C语言代码）

母牛的故事（C语言代码）

四维偏序（原题：[DBOI2019]德丽莎世界第一可爱）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

【绝对值排序】（C语言代码）

printf基础练习2 （有点不明白）

简单的a+b （C语言代码）

1642题解

1012题解

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

统计立方数（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

Catshao

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

宏定义

IP判断 （C语言代码）

母牛的故事 （C语言代码）

四维偏序（原题：[DBOI2019]德丽莎世界第一可爱）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.5 （Java代码）

【绝对值排序】 （C语言代码）

printf基础练习2 （有点不明白）

简单的a+b （C语言代码）

1642题解

1012题解

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

统计立方数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

IP判断（C语言代码）

母牛的故事（C语言代码）

　　评论区

【绝对值排序】（C语言代码）

统计立方数（C语言代码）