首页 > 代码库 > UVA 11992 - Fast Matrix Operations(线段树)

UVA 11992 - Fast Matrix Operations(线段树)

2024-07-14 19:09:57   220人阅读

给定一个矩阵，3种操作，在一个矩阵中添加值a，设置值a，查询和

思路：由于最多20列，所以完全可以当作20个线段树来做，然后线段树是区间修改区间查询，利用延迟操作，开两个延迟值一个存放set操作，一个存放add操作

代码：

 

[cpp] view plaincopy
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #include <algorithm>  
  4. using namespace std;  
  5.   
  6. #define lson(x) ((x<<1) + 1)  
  7. #define rson(x) ((x<<1) + 2)  
  8. #define INF 0x3f3f3f3f  
  9.   
  10. const int N = 1000005;  
  11.   
  12. int r, c, m;  
  13.   
  14. struct Node {  
  15.     int l, r;  
  16.     int sum, Max, Min, sumv, setv;  
  17. } node[4 * N];  
  18.   
  19. void pushup(int x) {  
  20.     node[x].sum = node[lson(x)].sum + node[rson(x)].sum;  
  21.     node[x].Max = max(node[lson(x)].Max, node[rson(x)].Max);  
  22.     node[x].Min = min(node[lson(x)].Min, node[rson(x)].Min);  
  23. }  
  24.   
  25. void pushdown(int x) {  
  26.     if (node[x].setv) {  
  27.     node[lson(x)].sumv = node[rson(x)].sumv = 0;  
  28.     node[lson(x)].setv = node[rson(x)].setv = node[x].setv;  
  29.     node[lson(x)].sum = (node[lson(x)].r - node[lson(x)].l + 1) * node[x].setv;  
  30.     node[rson(x)].sum = (node[rson(x)].r - node[rson(x)].l + 1) * node[x].setv;  
  31.     node[lson(x)].Max = node[lson(x)].Min = node[x].setv;  
  32.     node[rson(x)].Max = node[rson(x)].Min = node[x].setv;  
  33.     node[x].setv = 0;  
  34.     }  
  35.     if (node[x].sumv) {  
  36.     node[lson(x)].sumv += node[x].sumv;  
  37.     node[rson(x)].sumv += node[x].sumv;  
  38.     node[lson(x)].sum += (node[lson(x)].r - node[lson(x)].l + 1) * node[x].sumv;  
  39.     node[rson(x)].sum += (node[rson(x)].r - node[rson(x)].l + 1) * node[x].sumv;  
  40.     node[lson(x)].Max += node[x].sumv;  
  41.     node[lson(x)].Min += node[x].sumv;  
  42.     node[rson(x)].Max += node[x].sumv;  
  43.     node[rson(x)].Min += node[x].sumv;  
  44.     node[x].sumv = 0;  
  45.     }  
  46. }  
  47.   
  48. void build(int l, int r, int x) {  
  49.     node[x].l = l; node[x].r = r;  
  50.     if (l == r) {  
  51.     node[x].sum = node[x].Max = node[x].Min = node[x].sumv = node[x].setv = 0;  
  52.     return;  
  53.     }  
  54.     int mid = (l + r) / 2;  
  55.     build(l, mid, lson(x));  
  56.     build(mid + 1, r, rson(x));  
  57.     pushup(x);  
  58. }  
  59.   
  60. void add(int l, int r, int v, int x) {  
  61.     if (node[x].l >= l && node[x].r <= r) {  
  62.     node[x].sumv += v;  
  63.     node[x].sum += (node[x].r - node[x].l + 1) * v;  
  64.     node[x].Max += v;  
  65.     node[x].Min += v;  
  66.     return;  
  67.     }  
  68.     pushdown(x);  
  69.     int mid = (node[x].l + node[x].r) / 2;  
  70.     if (l <= mid) add(l, r, v, lson(x));  
  71.     if (r > mid) add(l, r, v, rson(x));  
  72.     pushup(x);  
  73. }  
  74.   
  75. void set(int l, int r, int v, int x) {  
  76.     if (node[x].l >= l && node[x].r <= r) {  
  77.     node[x].setv = v;  
  78.     node[x].sum = (node[x].r - node[x].l + 1) * v;  
  79.     node[x].Max = node[x].Min = v;  
  80.     node[x].sumv = 0;  
  81.     return;  
  82.     }  
  83.     pushdown(x);  
  84.     int mid = (node[x].l + node[x].r) / 2;  
  85.     if (l <= mid) set(l, r, v, lson(x));  
  86.     if (r > mid) set(l, r, v, rson(x));  
  87.     pushup(x);  
  88. }  
  89.   
  90. Node query(int l, int r, int x) {  
  91.     Node ans; ans.sum = 0; ans.Max = 0; ans.Min = INF;  
  92.     if (node[x].l >= l && node[x].r <= r) {  
  93.     ans.sum = node[x].sum;  
  94.     ans.Max = node[x].Max;  
  95.     ans.Min = node[x].Min;  
  96.     return ans;  
  97.     }  
  98.     pushdown(x);  
  99.     int mid = (node[x].l + node[x].r) / 2;  
  100.     if (l <= mid) {  
  101.     Node tmp = query(l, r, lson(x));  
  102.     ans.sum += tmp.sum;  
  103.     ans.Max = max(ans.Max, tmp.Max);  
  104.     ans.Min = min(ans.Min, tmp.Min);  
  105.     }  
  106.     if (r > mid) {  
  107.     Node tmp = query(l, r, rson(x));  
  108.     ans.sum += tmp.sum;  
  109.     ans.Max = max(ans.Max, tmp.Max);  
  110.     ans.Min = min(ans.Min, tmp.Min);  
  111.     }  
  112.     return ans;  
  113. }  
  114.   
  115. int main() {  
  116.     while (~scanf("%d%d%d", &r, &c, &m)) {  
  117.     build(1, r * c, 0);  
  118.     int q, x1, y1, x2, y2, v;  
  119.     while (m--) {  
  120.         scanf("%d", &q);  
  121.         if (q == 3) {  
  122.         scanf("%d%d%d%d", &x1, &y1, &x2, &y2);  
  123.         x1--; x2--;  
  124.         int sum = 0, Max = 0, Min = INF;  
  125.         for (int i = x1; i <= x2; i++) {  
  126.             Node ans = query(i * c + y1, i * c + y2, 0);  
  127.             sum += ans.sum;  
  128.             Max = max(Max, ans.Max);  
  129.             Min = min(Min, ans.Min);  
  130.         }  
  131.         printf("%d %d %d\n", sum, Min, Max);  
  132.         }  
  133.         else {  
  134.         scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &v);  
  135.         x1--; x2--;  
  136.         for (int i = x1; i <= x2; i++) {  
  137.             if (q == 1) add(i * c + y1, i * c + y2, v, 0);  
  138.             else set(i * c + y1, i * c + y2, v, 0);  
  139.         }  
  140.         }  
  141.     }  
  142.     }  
  143.     return 0; 



联系
我们