bzoj 1513 [POI2006]Tet-Tetris 3D

Description

Task: Tetris 3D “Tetris” 游戏的作者决定做一个新的游戏, 一个三维的版本, 在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 作者想改变一下游戏的目的使得它更大众化,在新游戏中你将知道落下的立方体信息以及位置,你的任务就是回答所有立方体落下后最高的方块的高度.所有的立方体在下落过程中都是垂直的并且不会旋转.平板左下角坐标为原点,并且平行于坐标轴.

Input

第一行给出三个整数 D, S and N ( 1<= N<= 20 000, 1<= D, S <=1 000), 分别表示平板的长和宽以及下落立方体的数目. 接下来N 行每行描述一个立方体. 每行包含5个整数: d, s, w, x and y (1<= d, 0 <=x, d + x<= D, 1 <=s, 0<= y, s + y<= S, 1<= w <=100 000), 分别表示立方体的长\宽\高以及落下的左下角坐标, 长和宽都是平行于平板坐标轴的,落下后立方体着地的四个角坐标分别为: (x, y), (x + d, y), (x, y + s) and (x + d, y + s).

Output

一个整数表示所有立方体落下后最高的方块的高度.

Sample Input

7 5 4

4 3 2 0 0

3 3 1 3 0

7 1 2 0 3

2 3 3 2 2

Sample Output

6

题解

loli的测试题。。感觉好水啊。。

还有两道贼水的扫描线。。不是bzoj的就不往上放了。。

这题意思是每次找到一个矩阵里最大的，再覆盖这个矩阵。

那直接上二维线段树就好了。。而且这样应该要开longlong的，但是开不下。。连4倍的线段树空间都开不下，只够开3倍。

放上来主要是感觉这种写二维线段树的方法比较优越，记录一下

#include <cstdio>
#include <algorithm>
#include <cstring>
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
using namespace std;
typedef long long ll;
int D, S, N, d, s, w, x, y, ql, qr, qd, qu;
struct segx {
    int v[3010], mark[3010];
    void update(int rt, int l, int r, int L, int R, int val) {
        v[rt] = max(v[rt], val);
        if (l == L && r == R) {
            mark[rt] = max(mark[rt], val);
            return;
        }
        int mid = l + r >> 1;
        if (L <= mid) update(lson, L, min(R, mid), val);
        if (R >  mid) update(rson, max(L, mid + 1), R, val);
    }
    int query(int rt, int l, int r, int L, int R) {
        if (l == L && R == r)
            return v[rt];
        int mid = l + r >> 1, ans = mark[rt];
        if (L <= mid) ans = max(ans, query(lson, L, min(R, mid)));
        if (R >  mid) ans = max(ans, query(rson, max(L, mid + 1), R));
        return ans;
    }
};
struct segy {
    segx v[3010], mark[3010];
    void update(int rt, int l, int r, int L, int R, int val) {
        v[rt].update(1, 1, S, qd, qu, val);
        if (l == L && r == R) {
            mark[rt].update(1, 1, S, qd, qu, val);
            return;
        }
        int mid = l + r >> 1;
        if (L <= mid) update(lson, L, min(R, mid), val);
        if (R >  mid) update(rson, max(L, mid + 1), R, val);
    }
    int query(int rt, int l, int r, int L, int R) {
        if (l == L && R == r)
            return v[rt].query(1, 1, S, qd, qu);
        int mid = l + r >> 1, ans = mark[rt].query(1, 1, S, qd, qu);
        if (L <= mid) ans = max(ans, query(lson, L, min(R, mid)));
        if (R >  mid) ans = max(ans, query(rson, max(L, mid + 1), R));
        return ans;
    }
}T;
main() {
//  printf("%d", sizeof (T)/1024/1024);
//  freopen("tet.in", "r", stdin);
//  freopen("tet.out", "w", stdout);
    scanf("%d%d%d", &D, &S, &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
        ql = x + 1, qr = x + d, qd = y + 1, qu = y + s;
        int ans = T.query(1, 1, D, ql, qr);
        T.update(1, 1, D, ql, qr, ans + w);
    }
    qd = 1, qu = S;
    printf("%d\n", T.query(1, 1, D, 1, D));
}