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

时间：2023-03-09 21:36:36
洛谷P3437 [POI2006]TET-Tetris 3D(二维线段树 标记永久化)

题意

题目链接

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

*/

相关文章