欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3437 [POI2006]TET-Tetris 3D(二维线段树 标记永久化)

程序员文章站 2022-07-10 12:11:16
题意 "题目链接" Sol 二维线段树空间复杂度是多少啊qwqqq 为啥这题全网空间都是$n^2$还有人硬要说是$nlog^2n$呀、、 对于这题来说,因为有修改操作,我们需要在外层线段树上也打标记,而且标记的形式是对一段区间赋值。所以我们对每个标记需要开线段树来维护更改的位置 而且由于我们push ......

题意

题目链接

sol

二维线段树空间复杂度是多少啊qwqqq

为啥这题全网空间都是\(n^2\)还有人硬要说是\(nlog^2n\)呀、、

对于这题来说,因为有修改操作,我们需要在外层线段树上也打标记,而且标记的形式是对一段区间赋值。所以我们对每个标记需要开线段树来维护更改的位置

而且由于我们pushdown的时候是从一棵线段树里找出标记下传,pushup的时候是从子树的线段树总找出最大值上传,显然复杂度会爆炸,那么我们考虑标记永久化

具体来说,我们在写线段树的时候,如果在一段区间上打了赋值标记,显然他的子树都会受到影响。而一段区间的最大值又会对其父亲产生影响,那么直接开两个数组记录一下

然后在递归的过程中处理一下标记就行了

// luogu-judger-enable-o2
// luogu-judger-enable-o2
// luogu-judger-enable-o2
/*

*/ 
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int maxn = 2001, inf = 1e9 + 10;
void chmin(int &a, int b) {a = (a < b ? a : b);}
void chmax(int &a, int b) {a = (a > b ? a : b);}
int sqr(int x) {return x * x;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m, q;
struct inseg {
    int rt[maxn], ls[maxn], rs[maxn], mx[maxn], tag[maxn], tot;
    void update(int k) {
        mx[k] = max(mx[ls[k]], mx[rs[k]]);
    }
    void ps(int k, int v) {
        chmax(mx[k], v);
        chmax(tag[k], v);
    }
    void pushdown(int k) {
        if(!tag[k]) return ;
        if(!ls[k]) ls[k] = ++tot;
        if(!rs[k]) rs[k] = ++tot;
        ps(ls[k], tag[k]); ps(rs[k], tag[k]);
        tag[k] = 0;
    }
    void intmem(int &k, int l, int r, int ll, int rr, int v) {
        if(!k) k = ++tot;
        if(ll <= l && r <= rr) {ps(k, v); return ;}
        pushdown(k);
        int mid = l + r >> 1;
        if(ll <= mid) intmem(ls[k], l, mid, ll, rr, v);
        if(rr  > mid) intmem(rs[k], mid + 1, r, ll, rr, v);
        update(k);
    }
    int query(int k, int l, int r, int ll, int rr) {
        if(!k) return 0;
        if(ll <= l && r <= rr) return mx[k];
        pushdown(k);
        int mid = l + r >> 1, ans = 0;
        if(ll <= mid) chmax(ans, query(ls[k], l, mid, ll, rr));
        if(rr  > mid) chmax(ans, query(rs[k], mid + 1, r, ll, rr));
        return ans;
    }
};
int ls[maxn], rs[maxn], rtag[maxn], rmx[maxn], tot, root;
inseg tag[maxn], mx[maxn];
void intmem(int &k, int l, int r, int a, int b, int ll, int rr, int v) {
    if(!k) k = ++tot;
    mx[k].intmem(rmx[k], 1, m, ll, rr, v);
    if(a <= l && r <= b) {
        tag[k].intmem(rtag[k], 1, m, ll, rr, v); 
        return ;
    }
    int mid = l + r >> 1;
    if(a <= mid) intmem(ls[k], l, mid, a, b, ll, rr, v);
    if(b  > mid) intmem(rs[k], mid + 1, r, a, b, ll, rr, v);
}
int query(int k, int l, int r, int a, int b, int ll, int rr) {
    if(!k) return 0;
    int ans = tag[k].query(rtag[k], 1, m, ll, rr);
    if(a <= l && r <= b) return max(ans, mx[k].query(rmx[k], 1, m, ll, rr));
    int mid = l + r >> 1;
    if(a <= mid) chmax(ans, query(ls[k], l, mid, a, b, ll, rr));
    if(b  > mid) chmax(ans, query(rs[k], mid + 1, r, a, b, ll, rr));
    return ans;
}
signed main() {
    n = read(); m = read(); q = read();
    while(q--) {
        int d = read(), s = read(), h = read(), x = read(), y = read();
        //printf("**%d %d %d %d %d\n", x + 1, x + d, y + 1, y + s, h);
        intmem(root, 1, n, x + 1, x + d, y + 1, y + s, query(root, 1, n, x + 1, x + d, y + 1, y + s)  + h);
    }
    printf("%d\n", query(1, 1, n, 1, n, 1, m));
    return 0;
}
/*
7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
*/