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

· · 题解

以下内容不保证时效性。

感谢 @qinhuanmma，好喜欢你咔。

upd：已修改，少特判了个东西，求通过。

用的不是 CDQ，不是八叉树，不是 K-D Tree，用的是分块。

首先如果只有 (x_i,y_i) 这两维坐标，我们可以一维排序一维树状数组做到 \mathcal O(n\log n)。

如果有 (x_i,y_i,z_i) 这三维坐标，我们可以使用 CDQ 分治，但有一个简单粗暴的方法：使用可以维护二维信息的数据结构，如树套树。

现在有四维坐标了，延续上面的做法，当然可以用 K-D Tree，但这里用了一种不太一样的做法：三维分块，理论复杂度比 K-D Tree 优一点，并且跑得比大部分 CDQ 分治快。

在这之前首先确定你会二维分块。那么坐稳扶好，我们上车！

首先分大大块，形状是一个大的立方体，设其棱长为 kx。

然后分大块，其长和宽为 kx，高为 x。

其次是中块，其长为 kx，宽和高为 x。

接下来是小块，是一个小的立方体，其棱长为 x。

重点在于散块。如果保证每个点的 x 坐标、y 坐标、z 坐标分别是 1\sim n 的排列（这一点可以通过精细的离散化实现），就可以在查询时枚举散块的短边，判断其对应点是否在该散块之内。注意三个维度的散块不能算重，如下图所示：

总的时间复杂度为：

\mathcal O\left(\dfrac{n^3}{k^3x^3}+\dfrac{n^3}{kx^2}+\dfrac{3kn}{x}+k^3+x\right)

当 k=\mathcal O(n^{\frac{5}{24}}),x=\mathcal O(n^{\frac{7}{12}}) 时，得到最优复杂度为 \mathcal O(n^{\frac{5}{8}})。

实际上，上面的式子比较 Useless，因为常数对实际效率的影响较大。因此我们需要另写一个程序枚举 k,x：

// 枚举块长程序
#define int long long
const int n = 50000;
signed main() {
    int ans = 2e9, tmp, K, X;
    for (int k = 1; k <= n; k++) {
        for (int x = 1; x <= n / k; x++) {
            tmp = n * n * n / k / k / k / x / x / x + 3 * n * n / k / x / x + 3 * k * n / x + k * k * k + 3 * x;
            if (tmp < ans) ans = tmp, K = k, X = x;
        }
    }
    cout << ans << ' ' << K << ' ' << X << endl;
}

当然这也不是最终块长，需要自己调块长。

然后就可以正常地进行三维分块了。

对于本题，坐标不一定是 1\sim n 的排列，需要离散化。离散化的细节比较繁琐，放在代码注释里了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 50005, M1 = 9, M2 = 47, B1 = 7805, B2 = 1115; // 枚举出的块长 
int nn, n, ans = -1e18;
struct point { int x, y, z, d, w; } P[N], p[N], num[N];
bool cmpd(const point &a, const point &b) { // 各种各样的排序函数 
    if (a.d != b.d) return a.d < b.d;
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}
bool cmpx(const point &a, const point &b) { // 这里没有按 d 排序，所以后面要用 stable_sort 
    if (a.x != b.x) return a.x < b.x;
    if (a.y != b.y) return a.y < b.y;
    return a.z < b.z;
}
bool cmpy(const point &a, const point &b) {
    if (a.y != b.y) return a.y < b.y;
    if (a.x != b.x) return a.x < b.x;
    return a.z < b.z;
}
bool cmpz(const point &a, const point &b) {
    if (a.z != b.z) return a.z < b.z;
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}
int xy[N], xz[N], yx[N], yz[N], zx[N], zy[N];
int blk1[N], blk2[N], L1[N], L2[N];
int s1[M1][M1][M1]; // 大大块 
int s2x[M2][M1][M1], s2y[M1][M2][M1], s2z[M1][M1][M2];  // 大块 
int s3x[M2][M1][M2], s3y[M1][M2][M2], s3z[M2][M2][M1];  // 中块 
int s4[M2][M2][M2]; // 小块 
int s5x[N], s5y[N], s5z[N]; // 散块 
inline void init() {
    for (int i = 1; i <= n; i++) blk1[i] = (i - 1) / B1 + 1, blk2[i] = (i - 1) / B2 + 1;
    for (int i = n; i >= 1; i--) L1[blk1[i]] = blk2[i], L2[blk2[i]] = i;
}
void ckmax(int &a, int b) { a = max(a, b); }
inline void update(int x, int y, int z, int d) {
    int bx1 = blk1[x], bx2 = blk2[x], by1 = blk1[y], by2 = blk2[y], bz1 = blk1[z], bz2 = blk2[z];
    ckmax(s1[bx1][by1][bz1], d);
    ckmax(s2x[bx2][by1][bz1], d);
    ckmax(s2y[bx1][by2][bz1], d);
    ckmax(s2z[bx1][by1][bz2], d);
    ckmax(s3x[bx2][by1][bz2], d);
    ckmax(s3y[bx1][by2][bz2], d);
    ckmax(s3z[bx2][by2][bz1], d);
    ckmax(s4[bx2][by2][bz2], d);
    ckmax(s5x[x], d), ckmax(s5y[y], d), ckmax(s5z[z], d);
}
inline int query(int x, int y, int z) {
    #define loop(a, x1, y1, z1, x2, y2, z2) for (int i = x1; i < x2; i++) for (int j = y1; j < y2; j++) for (int k = z1; k < z2; k++) ckmax(ans, a[i][j][k])
    int bx1 = blk1[x], bx2 = blk2[x], by1 = blk1[y], by2 = blk2[y], bz1 = blk1[z], bz2 = blk2[z];
    int lx1 = L1[bx1], ly1 = L1[by1], lz1 = L1[bz1], lx2 = L2[bx2], ly2 = L2[by2], lz2 = L2[bz2];
    int ans = -1e18;
    loop(s1, 1, 1, 1, bx1, by1, bz1);
    loop(s2x, lx1, 1, 1, bx2, by1, bz1);
    loop(s2y, 1, ly1, 1, bx1, by2, bz1);
    loop(s2z, 1, 1, lz1, bx1, by1, bz2);
    loop(s3x, lx1, 1, lz1, bx2, by1, bz2);
    loop(s3y, 1, ly1, lz1, bx1, by2, bz2);
    loop(s3z, lx1, ly1, 1, bx2, by2, bz1);
    loop(s4, lx1, ly1, lz1, bx2, by2, bz2);
    for (int i = lx2; i <= x; i++) if (xy[i] <= y && xz[i] <= z) ckmax(ans, s5x[i]);    // 注意三个散块不能算重！ 
    for (int i = ly2; i <= y; i++) if (yx[i] < lx2 && yz[i] <= z) ckmax(ans, s5y[i]);
    for (int i = lz2; i <= z; i++) if (zx[i] < lx2 && zy[i] < ly2) ckmax(ans, s5z[i]);
    return ans;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> nn; bool flg = 0;
    for (int i = 1; i <= nn; i++) cin >> P[i].x >> P[i].y >> P[i].z >> P[i].d >> P[i].w, flg |= P[i].w >= 0;
    if (!flg) {
        for (int i = 1; i <= nn; i++) ans = max(ans, P[i].w);
        return cout << ans, 0;
    }
    sort(P + 1, P + 1 + nn, cmpd);
    p[++n] = P[1], p[n].w = max(p[n].w, 0ll);
    for (int i = 2; i <= nn; i++) { // 合并重复的点 
        if (P[i].x == P[i - 1].x && P[i].y == P[i - 1].y && P[i].z == P[i - 1].z && P[i].d == P[i - 1].d) p[n].w += max(P[i].w, 0ll);
        else p[++n] = P[i], p[n].w = max(p[n].w, 0ll);
    }
    for (int i = 1; i <= n; i++) num[i] = {p[i].x, p[i].y, p[i].z, 0, i};
    // 前面已经提到了，为了避免 xyz 都相同但 d 不相同的点产生贡献，由于前面已经按照 d 排序，所以使用 stable_sort 
    stable_sort(num + 1, num + 1 + n, cmpx);
    for (int i = 1; i <= n; i++) p[num[i].w].x = i;
    stable_sort(num + 1, num + 1 + n, cmpy);
    for (int i = 1; i <= n; i++) p[num[i].w].y = i;
    stable_sort(num + 1, num + 1 + n, cmpz);
    for (int i = 1; i <= n; i++) p[num[i].w].z = i;
    for (int i = 1; i <= n; i++) {
        xy[p[i].x] = p[i].y;
        xz[p[i].x] = p[i].z;
        yx[p[i].y] = p[i].x;
        yz[p[i].y] = p[i].z;
        zx[p[i].z] = p[i].x;
        zy[p[i].z] = p[i].y;
    }
    init();
    for (int i = 1, x; i <= n; i++) {   // 正常求解 
        x = query(p[i].x, p[i].y, p[i].z);
        ckmax(ans, x + p[i].w);
        update(p[i].x, p[i].y, p[i].z, x + p[i].w);
    }
    cout << ans << '\n';
}

:::success[2025 / 11 / 28]{open} 上面的代码没怎么调块长，调完之后能拿到除 KDT 以外的最优解？\text{polylog} 做法没有前途。 :::

说实话这道题硬上三维分块比较奇怪，三维分块其实可以配合一些东西（比如莫队）来平衡复杂度，比方说这样就能 \mathcal O(n^{\frac{13}{8}}) 做五维偏序，\mathcal O(n^{\frac 53}) 做六维偏序。（虽然这个 K-D Tree 好像也能）

但这玩意其实很弱，甚至跑不过 K-D Tree，只抢到了次优解（截至 2024/6/13）……总而言之这东西的用途感觉不是特别大，事实上它能做的题除了必须根号算法的以外好像都可以硬上 K-D Tree 或 CDQ 分治，但主打一个好写，别看代码长实际上大多数都是重复的。

之前被撤下且手误删除的题解，找 chen_zhe 拿回了。

将近一年半以前的题解了呢。

当时的我，是怀着怎样的心情写下这篇文字的呢？

当时的我，对未来想必是满怀着希望的吧。

还是舍不得大家呢。

但是，该说再见了呢。

愿能再次相会，在那之后，永不分离。