BZOJ 1513: [POI2006]Tet-Tetris 3D

线段树套线段树，即二维线段树
具体写法就是内层一个表示y轴的线段树，正常写即可，不过要标记永久化一下
外层一个线段树同理，把数组换成内层线段树即可

#include <bits/stdc++.h>
#define lp p << 1
#define rp p << 1 | 1
#define mid ((l + r) >> 1)
#define y1 yyy1

const int N = 3e3 + 7;
int n, m;

struct In_Seg {
    int tag[N], mx[N];
    void update(int p, int l, int r, int x, int y, int v) {
        mx[p] = std::max(mx[p], v);
        if (x <= l && y >= r) {
            tag[p] = std::max(tag[p], v);
            return;
        }
        if (x <= mid) update(lp, l, mid, x, y, v);
        if (y > mid) update(rp, mid + 1, r, x, y, v);
    }
    int query(int p, int l, int r, int x, int y) {
        if (x <= l && y >= r) return mx[p];
        int ans = tag[p];
        if (x <= mid) ans = std::max(ans, query(lp, l, mid, x, y));
        if (y > mid) ans = std::max(ans, query(rp, mid + 1, r, x, y));
        return ans;
    }
};

int x1, x2, y1, y2;

struct Out_Seg {
    In_Seg tag[N], mx[N];
    void update(int p, int l, int r, int x, int y, int v) {
        mx[p].update(1, 1, m, y1, y2, v);
        if (x <= l && y >= r) {
            tag[p].update(1, 1, m, y1, y2, v);
            return;
        }
        if (x <= mid) update(lp, l, mid, x, y, v);
        if (y > mid) update(rp, mid + 1, r, x, y, v);
    }
    int query(int p, int l, int r, int x, int y) {
        if (x <= l && y >= r) return mx[p].query(1, 1, m, y1, y2);
        int ans = tag[p].query(1, 1, m, y1, y2);
        if (x <= mid) ans = std::max(ans, query(lp, l, mid, x, y));
        if (y > mid) ans = std::max(ans, query(rp, mid + 1, r, x, y));
        return ans;
    }
} seg;

int main() {
    int q;
    scanf("%d%d%d", &n, &m, &q);
    while (q--) {
        int d, s, w, x, y;
        scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
        x1 = x + 1, x2 = x + d, y1 = y + 1, y2 = y + s;
        int res = seg.query(1, 1, n, x1, x2);
        seg.update(1, 1, n, x1, x2, w + res);
    }
    y1 = 1, y2 = m;
    printf("%d\n", seg.query(1, 1, n, 1, n));
    return 0;
}

BZOJ 1513: [POI2006]Tet-Tetris 3D

原文：https://www.cnblogs.com/Mrzdtz220/p/12307539.html