洛谷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 */
上一篇: 数据库SQL查询表的建立教程
下一篇: SQL结构化查询语言的语法实例讲解