Luogu P3437 [POI2006]TET-Tetris 3D

题目描述

https://www.luogu.com.cn/problem/P3437

Solution

题目简化一下就是要求做到矩形求最大值，矩形赋值（保证赋出来的最大值比原来的值大，矩形的长和宽小于等于 $1000$

我们直接二维线段树即可，甚至不用动态开点

注意必须要标记永久化

#include <iostream>
#include <algorithm>
#define maxn 2050
using namespace std;

int n, m, q;

#define lc i << 1
#define rc i << 1 | 1 
struct seg {
    struct node {
        int v, tag;
    } T[maxn];

    void update(int i, int l, int r, int L, int R, int v) {
        if (l > R || r < L) return ;
        T[i].v = max(T[i].v, v); 
        if (L <= l && r <= R) return T[i].tag = max(T[i].tag, v), void();
        int m = l + r >> 1;
        update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    }

    int query(int i, int l, int r, int L, int R) {
        if (l > R || r < L) return 0;
        if (L <= l && r <= R) return T[i].v; 
        int m = l + r >> 1;
        return max({ T[i].tag, query(lc, l, m, L, R), query(rc, m + 1, r, L, R) }); 
    }
};

struct Seg {
    struct node {
        seg v, tag; 
    } T[maxn];

    void update(int i, int l, int r, int L, int R, int s, int t, int v) {
        if (l > R || r < L) return ;
        T[i].v.update(1, 0, m, s, t, v); 
        if (L <= l && r <= R) return T[i].tag.update(1, 0, ::m, s, t, v);
        int m = l + r >> 1;
        update(lc, l, m, L, R, s, t, v); update(rc, m + 1, r, L, R, s, t, v); 
    }

    int query(int i, int l, int r, int L, int R, int s, int t) {
        if (l > R || r < L) return 0; 
        if (L <= l && r <= R) return T[i].v.query(1, 0, ::m, s, t);
        int m = l + r >> 1; 
        return max({ T[i].tag.query(1, 0, ::m, s, t), query(lc, l, m, L, R, s, t), query(rc, m + 1, r, L, R, s, t) }); 
    } 
} T;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> q; int ans = 0; 
    for (int i = 1; i <= q; ++i) {
        int d, s, w, v, x1, x2, y1, y2; cin >> d >> s >> w >> x1 >> y1;
        x2 = x1 + d - 1; y2 = y1 + s - 1;
        v = T.query(1, 0, n, x1, x2, y1, y2) + w; ans = max(ans, v); 
        T.update(1, 0, n, x1, x2, y1, y2, v); 
    } cout << ans << "\n"; 
    return 0;
}