首页 > 代码库 > [uva11992]Fast Matrix Operations（多延迟标记，二维线段树，区间更新）
[uva11992]Fast Matrix Operations（多延迟标记，二维线段树，区间更新）
题目链接：https://vjudge.net/problem/UVA-11992
题意：n*m的矩阵，每次对一个子矩阵操作，有三种操作：加x，设置为x，查询。查询返回子矩阵和、最小值、最大值
n很小(<=20)，所以可以开20棵线段树，每次操作按行更新。
特别小心put和add两个延迟标记，坑老惨了。
put初始化-1最简单的坑，略过。
build的时候要每一个节点都要clear，不能只clear叶子。因为会有直接差没操作的子矩阵（因为初始化都是0）。
数组开大。。。
add的话，什么都不用管。
put的话，在update的时候要把那时候的add标记清空，不要忘记在向下传递的时候，也要清空！
上述几点都注意到，这题就能A。感觉写了一道模拟题。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 #define lrt rt << 1 5 #define rrt rt << 1 | 1 6 typedef struct Node { 7 int lo, hi, sum; 8 int add, put; 9 }Node; 10 const int maxn = 22; 11 const int maxm = 200200; 12 Node seg[maxn][maxm<<2]; 13 int n, m, q; 14 15 void pushup(Node* seg, int rt) { 16 seg[rt].sum = seg[lrt].sum + seg[rrt].sum; 17 seg[rt].lo = min(seg[lrt].lo, seg[rrt].lo); 18 seg[rt].hi = max(seg[lrt].hi, seg[rrt].hi); 19 } 20 21 void pushdown(Node* seg, int rt, int l, int r) { 22 int mid = (l + r) >> 1; 23 if(seg[rt].put != -1) { 24 seg[lrt].sum = (mid - l + 1) * seg[rt].put; 25 seg[rrt].sum = (r - mid) * seg[rt].put; 26 seg[lrt].lo = seg[lrt].hi = seg[rt].put; 27 seg[rrt].lo = seg[rrt].hi = seg[rt].put; 28 seg[lrt].put = seg[rrt].put = seg[rt].put; 29 seg[lrt].add = seg[rrt].add = 0; 30 seg[rt].put = -1; 31 } 32 if(seg[rt].add) { 33 seg[lrt].sum += (mid - l + 1) * seg[rt].add; 34 seg[rrt].sum += (r - mid) * seg[rt].add; 35 seg[lrt].lo += seg[rt].add; 36 seg[lrt].hi += seg[rt].add; 37 seg[rrt].lo += seg[rt].add; 38 seg[rrt].hi += seg[rt].add; 39 seg[lrt].add += seg[rt].add; 40 seg[rrt].add += seg[rt].add; 41 seg[rt].add = 0; 42 } 43 } 44 45 void build(Node* seg, int l, int r, int rt) { 46 seg[rt].lo = seg[rt].hi = seg[rt].sum = seg[rt].add = 0; 47 seg[rt].put = -1; 48 if(l == r) return; 49 int mid = (l + r) >> 1; 50 build(seg, l, mid, lrt); 51 build(seg, mid+1, r, rrt); 52 } 53 54 void update(Node* seg, int L, int R, int l, int r, int rt, int val, int type) { 55 if(L <= l && r <= R) { 56 if(type == 1) { 57 seg[rt].lo += val; 58 seg[rt].hi += val; 59 seg[rt].add += val; 60 seg[rt].sum += (r - l + 1) * val; 61 } 62 else if(type == 2) { 63 seg[rt].lo = val; 64 seg[rt].hi = val; 65 seg[rt].put = val; 66 seg[rt].sum = (r - l + 1) * val; 67 seg[rt].add = 0; 68 } 69 return; 70 } 71 pushdown(seg, rt, l, r); 72 int mid = (l + r) >> 1; 73 if(L <= mid) update(seg, L, R, l, mid, lrt, val, type); 74 if(mid < R) update(seg, L, R, mid+1, r, rrt, val, type); 75 pushup(seg, rt); 76 } 77 78 Node query(Node* seg, int L, int R, int l, int r, int rt) { 79 if(L <= l && r <= R) return seg[rt]; 80 pushdown(seg, rt, l, r); 81 int mid = (l + r) >> 1; 82 Node ret; 83 ret.lo = 0x7f7f7f7f, ret.hi = 0, ret.sum = 0; 84 if(L <= mid) { 85 Node tmp = query(seg, L, R, l, mid, lrt); 86 ret.lo = min(ret.lo, tmp.lo); 87 ret.hi = max(ret.hi, tmp.hi); 88 ret.sum += tmp.sum; 89 } 90 if(mid < R) { 91 Node tmp = query(seg, L, R, mid+1, r, rrt); 92 ret.lo = min(ret.lo, tmp.lo); 93 ret.hi = max(ret.hi, tmp.hi); 94 ret.sum += tmp.sum; 95 } 96 pushup(seg, rt); 97 return ret; 98 } 99 100 int main() { 101 // freopen("in", "r", stdin); 102 // freopen("out", "w", stdout); 103 int type, x1, y1, x2, y2, val; 104 while(~scanf("%d%d%d",&n,&m,&q)) { 105 for(int i = 1; i <= n; i++) { 106 build(seg[i], 1, m, 1); 107 } 108 while(q--) { 109 scanf("%d%d%d%d%d",&type,&x1,&y1,&x2,&y2); 110 if(type == 3) { 111 Node ret, tmp; 112 ret.lo = 0x7f7f7f7f, ret.hi = 0, ret.sum = 0; 113 for(int i = x1; i <= x2; i++) { 114 tmp = query(seg[i], y1, y2, 1, m, 1); 115 ret.lo = min(ret.lo, tmp.lo); 116 ret.hi = max(ret.hi, tmp.hi); 117 ret.sum += tmp.sum; 118 } 119 printf("%d %d %d\n", ret.sum, ret.lo, ret.hi); 120 } 121 else { 122 scanf("%d", &val); 123 for(int i = x1; i <= x2; i++) { 124 update(seg[i], y1, y2, 1, m, 1, val, type); 125 } 126 } 127 } 128 } 129 return 0; 130 }
[uva11992]Fast Matrix Operations（多延迟标记，二维线段树，区间更新）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。