bzoj1513

二维线段树

听说二维线段树不能下传标记？

就是裸的二维线段树，由于每次高度只能增加，所以我们就可以标记永久化

每个线段树里有两个数组,mx和mark，每次修改路径上所有mx都要修改，mark是区间的精确覆盖修改

每次查询把路径上所有mark取max，然后和精确覆盖区间mx取max

为什么这样做呢？我们能不能只用一个数组？当然不行，如果我们只用mark，那么假设我们更新区间[1,4],然后查询区间[1,5],那么答案明显不对，如果我们只用mx，那么我们更新[1,1],查询[2,2],那么我们的答案被[1,1]更新了，也是不对。

#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int n, m, t;
struct Segment_Tree_X {
    int mx[N], mark[N];
    void update(int l, int r, int x, int a, int b, int tmp)
    {
        if(l > b || r < a) return;
        mx[x] = max(mx[x], tmp);
        if(l >= a && r <= b) 
        {
            mark[x] = max(mark[x], tmp);
            return;
        }
        int mid = (l + r) >> 1;
        update(l, mid, x << 1, a, b, tmp);
        update(mid + 1, r, x << 1 | 1, a, b, tmp);
    }
    int query(int l, int r, int x, int a, int b)
    {
        if(l > b || r < a) return 0;
        if(l >= a && r <= b) return mx[x];
        int mid = (l + r) >> 1;
        return max(mark[x], max(query(l, mid, x << 1, a, b), query(mid + 1, r, x << 1 | 1, a, b)));
    }
};
struct Segment_Tree_Y {
    Segment_Tree_X mx[N], mark[N];
    void update(int l, int r, int x, int a, int b, int y_l, int y_r, int tmp)
    {
        if(l > b || r < a) return;
        mx[x].update(1, m, 1, y_l, y_r, tmp);
        if(l >= a && r <= b)
        {
            mark[x].update(1, m, 1, y_l, y_r, tmp);
            return;
        }
        int mid = (l + r) >> 1;
        update(l, mid, x << 1, a, b, y_l, y_r, tmp);
        update(mid + 1, r, x << 1 | 1, a, b, y_l, y_r, tmp);
    }
    int query(int l, int r, int x, int a, int b, int y_l, int y_r)
    {
        if(l > b || r < a) return 0;
        if(l >= a && r <= b) return mx[x].query(1, m, 1, y_l, y_r);
        int mid = (l + r) >> 1;
        return max(mark[x].query(1, m, 1, y_l, y_r), max(query(l, mid, x << 1, a, b, y_l, y_r), query(mid + 1, r, x << 1 | 1, a, b, y_l, y_r)));
    }
} T;
int main()
{
    scanf("%d%d%d", &n, &m, &t);
    while(t --)
    {
        int d, s, w, x, y, tmp;
        scanf("%d%d%d%d%d", &d, &s, &w, &x, &y);
        ++ x;
        ++ y;
        tmp = T.query(1, n, 1, x, x + d - 1, y, y + s - 1);
        T.update(1, n, 1, x, x + d - 1, y, y + s - 1, w + tmp);
    }
    printf("%d
", T.query(1, n, 1, 1, n, 1, m));
    return 0;
}