题解：P3437 [POI2006] TET-Tetris 3D

liujiaxi123456 · 2025-01-23 15:26:19 · 题解

前言 & 概述

看到所有的题解都是树套树/四分树/K-d tree，其中树套树卡空间，四分树卡时间，K-d tree 根本没卡过，于是想写一篇不用卡常，不用卡空间，好写好调的二维分块做法。

二维分块

众所周知，分块的复杂度是根号级别的，所以如果直接在第一维的基础上对第二维分块，时间复杂度是根号的平方，也就是 O(n)，所以平时不常使用，但是此题由于数据范围较小，完全可以通过。

P.S. 还有另外一种二维分块是可以做到根号的，但是需要一些条件，且非常复杂，在此不提，有兴趣的话，可以做做此题。

此题

先概括一下模型：

• 多次操作。

• 每次矩形查询最大值与矩形覆盖。

• P.S. 每次覆盖的值一定比之前的大。

显然需要二维数据结构，我们这里考虑二维分块：

• 先考虑查询需要的答案：

  • 散-散、散-整、整-散、整-整。

  • 所以我们需要四个基本数组分别表示这样的答案（分别为 a, g, h, f）。

• 考虑修改对这些答案的影响：

  • 散-散：a 数组。

  • 最简单，把 a,g,h,f 四个数组都更新一下即可。

  • 散-整：g 数组。

  • 直接更新 g,f 数组。

  • 发现由于需要更新 a,h 数组有根号个，不能直接枚举后更新，考虑懒标记：

    • 对于 a 数组，直接记录 tag_g 即可。

    • 这意味着在询问单点值，即 a 的值时，需要考虑 tag 的贡献。

    • 下面有 tag 的同样要在查询时收集 tag 贡献。

    • 对于 h 数组，所有与它相交的 tag_g 都要收集。

    • 于是令 tagmax_g 表示一个块内的 tag_g 的 \max。

    • 在更新时把这两个数组一同更新。

  • 整-散：h 数组。

  • 与 g 数组一样的处理方式。

  • 整-整：f 数组。

  • 更新 f 数组。

  • 对于 a,g,h 数组，显然仍然不能直接更新，仍然考虑懒标记：

    • 记录 tag_f 即可。

• 处理掉修改后的查询：

  • a = \max(a, tag_f, tag_g, tag_h)
  • g = \max(g, tag_f, tagmax_h)
  • h = \max(h, tag_f, tagmax_g)
  • f = f

注意点：

• 本题输入的是点坐标，不是格子坐标，所以实际查询/修改的是：[x+1, x+d][y+1, y+s]。

• 为了区分整散块，建议可以用 i 表示第一维整块，j 表示第一维散块，p,q 同理表示第二维。

• 更多细节见代码。

Code：

最后献上我的代码（本来以为要卡常导致码风有点丑，后来发现发现跑得飞快（lg rank 5），但是懒得改了，如果对细节有困惑的话可以参考我注释掉的 A,G,H,F 函数）。

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

const int Maxn = 1005, Sqrt = 50;
// const int Maxn = 1005, Sqrt = 1005;

class DataStructure {
private:
    int N, M, num1, num2, B1, B2, f[Sqrt][Sqrt], g[Maxn][Sqrt], h[Sqrt][Maxn], a[Maxn][Maxn];
    int st1[Sqrt], ed1[Sqrt], st2[Sqrt], ed2[Sqrt], bel1[Maxn], bel2[Maxn];
    int tag_f[Sqrt][Sqrt], tag_g[Maxn][Sqrt], tag_h[Sqrt][Maxn], tag_g_max[Sqrt][Sqrt], tag_h_max[Sqrt][Sqrt];
    inline void chkmax(int &a, int b) { a<b ?(a=b) : 0; }
    // inline int A(int j, int q) { return max({a[j][q], tag_f[bel1[j]][bel2[q]], tag_g[j][bel2[q]], tag_h[bel1[j]][q]}); }
    // inline int G(int j, int p) { return max({g[j][p], tag_f[bel1[j]][p], tag_h_max[bel1[j]][p]}); }
    // inline int H(int i, int q) { return max({h[i][q], tag_f[i][bel2[q]], tag_g_max[i][bel2[q]]}); }
    // inline int F(int i, int p) { return f[i][p]; }
public:
    inline void init(int n, int m) {
        // N = n, M = m;
        B1 = sqrt(n), B2 = sqrt(m);
        // num1 = (N+B1-1)/B1, num2 = (M+B2-1)/B2;
        // for(int i=1; i<=num1; i++) {
        //  st1[i] = ed1[i-1]+1, ed1[i] = min(N, i*B1);
        //  for(int j=st1[i]; j<=ed1[i]; j++)   bel1[j] = i, printf("bel1[%d]:%d\n", j, bel1[j]);
        // }
        // for(int i=1; i<=num2; i++) {
        //  st2[i] = ed2[i-1]+1, ed2[i] = min(M, i*B2);
        //  for(int j=st2[i]; j<=ed2[i]; j++)   bel2[j] = i, printf("bel2[%d]:%d\n", j, bel1[j]);
        // }
    }
    inline int Query(int l1, int r1, int l2, int r2) {
        int res = 0;
        int x1 = (l1+B1-1)/B1+1, y1 = (r1)/B1, x2 = (l2+B2-1)/B2+1, y2 = (r2)/B2;
        // printf("Query::(l1:%d, r1:%d, l2:%d, r2:%d, x1:%d, y1:%d, x2:%d, y2:%d)\n", l1, r1, l2, r2, x1, y1, x2, y2);
        if(x1 > y1 and x2 > y2) {
            for(int j=l1; j<=r1; j++) for(int q=l2; q<=r2; q++) res = max({res, a[j][q], tag_f[x1-1][x2-1], tag_g[j][x2-1], tag_h[x1-1][q]});
        } else if(x1 > y1) {
            for(int j=l1; j<=r1; j++) {
                for(int q=l2; q<=x2*B2-B2; q++) res = max({res, a[j][q], tag_f[x1-1][x2-1], tag_g[j][x2-1], tag_h[x1-1][q]});
                for(int p=x2; p<=y2; p++)   res = max({res, g[j][p], tag_f[x1-1][p], tag_h_max[x1-1][p]});
                for(int q=y2*B2+1; q<=r2; q++)  res = max({res, a[j][q], tag_f[x1-1][y2+1], tag_g[j][y2+1], tag_h[x1-1][q]});
            }
        } else if(x2 > y2) {
            for(int j=l1; j<=x1*B1-B1; j++) for(int q=l2; q<=r2; q++) res = max({res, a[j][q], tag_f[x1-1][x2-1], tag_g[j][x2-1], tag_h[x1-1][q]});
            for(int i=x1; i<=y1; i++) for(int q=l2; q<=r2; q++) res = max({res, h[i][q], tag_f[i][x2-1], tag_g_max[i][x2-1]});
            for(int j=y1*B1+1; j<=r1; j++) for(int q=l2; q<=r2; q++) res = max({res, a[j][q], tag_f[y1+1][x2-1], tag_g[j][x2-1], tag_h[y1+1][q]});
        } else {
            for(int j=l1; j<=x1*B1-B1; j++) {
                for(int q=l2; q<=x2*B2-B2; q++) res = max({res, a[j][q], tag_f[x1-1][x2-1], tag_g[j][x2-1], tag_h[x1-1][q]});
                for(int p=x2; p<=y2; p++)   res = max({res, g[j][p], tag_f[x1-1][p], tag_h_max[x1-1][p]});
                for(int q=y2*B2+1; q<=r2; q++)  res = max({res, a[j][q], tag_f[x1-1][y2+1], tag_g[j][y2+1], tag_h[x1-1][q]});
            }
            for(int i=x1; i<=y1; i++) {
                for(int q=l2; q<=x2*B2-B2; q++) res = max({res, h[i][q], tag_f[i][x2-1], tag_g_max[i][x2-1]});
                for(int p=x2; p<=y2; p++)   res = max(res, f[i][p]);
                for(int q=y2*B2+1; q<=r2; q++)  res = max({res, h[i][q], tag_f[i][y2+1], tag_g_max[i][y2+1]});
            }
            for(int j=y1*B1+1; j<=r1; j++) {
                for(int q=l2; q<=x2*B2-B2; q++) res = max({res, a[j][q], tag_f[y1+1][x2-1], tag_g[j][x2-1], tag_h[y1+1][q]});
                for(int p=x2; p<=y2; p++)   res = max({res, g[j][p], tag_f[y1+1][p], tag_h_max[y1+1][p]});
                for(int q=y2*B2+1; q<=r2; q++)  res = max({res, a[j][q], tag_f[y1+1][y2+1], tag_g[j][y2+1], tag_h[y1+1][q]});
            }
        }
        return res;
    }
    inline void Cover(int l1, int r1, int l2, int r2, int k) {
        int x1 = (l1+B1-1)/B1+1, y1 = (r1)/B1, x2 = (l2+B2-1)/B2+1, y2 = (r2)/B2;
        if(x1 > y1 and x2 > y2) {
            // puts("type 1");
            for(int j=l1; j<=r1; j++) for(int q=l2; q<=r2; q++) chkmax(f[x1-1][x2-1], k), chkmax(g[j][x2-1], k), chkmax(h[x1-1][q], k), chkmax(a[j][q], k);
        } else if(x1 > y1) {
            // puts("type 2");
            for(int j=l1; j<=r1; j++) {
                for(int q=l2; q<=x2*B2-B2; q++) chkmax(f[x1-1][x2-1], k), chkmax(g[j][x2-1], k), chkmax(h[x1-1][q], k), chkmax(a[j][q], k);
                for(int p=x2; p<=y2; p++)   chkmax(f[x1-1][p], k), chkmax(g[j][p], k), chkmax(tag_g_max[x1-1][p], k), chkmax(tag_g[j][p], k);
                for(int q=y2*B2+1; q<=r2; q++)  chkmax(f[x1-1][y2+1], k), chkmax(g[j][y2+1], k), chkmax(h[x1-1][q], k), chkmax(a[j][q], k);
            }
        } else if(x2 > y2) {
            // puts("type 3");
            for(int j=l1; j<=x1*B1-B1; j++) for(int q=l2; q<=r2; q++) chkmax(f[x1-1][x2-1], k), chkmax(g[j][x2-1], k), chkmax(h[x1-1][q], k), chkmax(a[j][q], k);
            for(int i=x1; i<=y1; i++) for(int q=l2; q<=r2; q++) chkmax(f[i][x2-1], k), chkmax(h[i][q], k), chkmax(tag_h_max[i][x2-1], k), chkmax(tag_h[i][q], k);
            for(int j=y1*B1+1; j<=r1; j++) for(int q=l2; q<=r2; q++) chkmax(f[y1+1][x2-1], k), chkmax(g[j][x2-1], k), chkmax(h[y1+1][q], k), chkmax(a[j][q], k);
        } else {
            // puts("type 4");
            for(int j=l1; j<=x1*B1-B1; j++) {
                for(int q=l2; q<=x2*B2-B2; q++) chkmax(f[x1-1][x2-1], k), chkmax(g[j][x2-1], k), chkmax(h[x1-1][q], k), chkmax(a[j][q], k);
                for(int p=x2; p<=y2; p++)   chkmax(f[x1-1][p], k), chkmax(g[j][p], k), chkmax(tag_g_max[x1-1][p], k), chkmax(tag_g[j][p], k);
                for(int q=y2*B2+1; q<=r2; q++)  chkmax(f[x1-1][y2+1], k), chkmax(g[j][y2+1], k), chkmax(h[x1-1][q], k), chkmax(a[j][q], k);
            }
            for(int i=x1; i<=y1; i++) {
                for(int q=l2; q<=x2*B2-B2; q++) chkmax(f[i][x2-1], k), chkmax(h[i][q], k), chkmax(tag_h_max[i][x2-1], k), chkmax(tag_h[i][q], k);
                for(int p=x2; p<=y2; p++)   chkmax(f[i][p], k), chkmax(tag_f[i][p], k);
                for(int q=y2*B2+1; q<=r2; q++)  chkmax(f[i][y2+1], k), chkmax(h[i][q], k), chkmax(tag_h_max[i][y2+1], k), chkmax(tag_h[i][q], k);
            }
            for(int j=y1*B1+1; j<=r1; j++) {
                for(int q=l2; q<=x2*B2-B2; q++) chkmax(f[y1+1][x2-1], k), chkmax(g[j][x2-1], k), chkmax(h[y1+1][q], k), chkmax(a[j][q], k);
                for(int p=x2; p<=y2; p++)   chkmax(f[y1+1][p], k), chkmax(g[j][p], k), chkmax(tag_g_max[y1+1][p], k), chkmax(tag_g[j][p], k);
                for(int q=y2*B2+1; q<=r2; q++)  chkmax(f[y1+1][y2+1], k), chkmax(g[j][y2+1], k), chkmax(h[y1+1][q], k), chkmax(a[j][q], k);
            }
        } 
    }
} ds;

namespace Josh_zmf {

    int Q, N, M;

    inline int main() {
        cin>> N>> M>> Q, ds.init(N, M);
        for(int d, s, w, x, y; Q--; ) {
            cin>> d>> s>> w>> x>> y;
            int h = ds.Query(x+1, x+d, y+1, y+s);
            // printf("h:%d\n", h);
            ds.Cover(x+1, x+d, y+1, y+s, h+w);
        }
        cout<< ds.Query(1, N, 1, M)<< '\n';
        return 0;
    }

}

int main() {
    Josh_zmf::main();
    return 0;
}

结语：

都看到这里了，点个赞再走吧！