uva 11992 Fast Matrix Operations

本文从WordPress迁移而来, 查看全部WordPress迁移文章

线段树

题意:给一个矩阵,每次对其子矩阵操作

  1. 将子矩阵每个元素的值增加val
  2. 将子矩阵每个元素的值设置为val
  3. 查询子矩阵的元素和,以及最小最大元素

首先是个二维的矩阵,本来想写成四分树的,但最后想想不需要,把二维压缩为1一维,将按行优先,把矩阵存在一个线性区间内,例如一个3 * 3的矩阵

1 2 3(第一行)(4 5 6)第二行(7 8 9)第三行

对一个子矩阵操作,其实就可以按子矩阵的行来更新,新更新第1行,第2行…….每一行都可以在刚才的线性区间中找到位置

好像更新(1,1,2,2)这个子矩阵,第1行的两个元素在总区间中对应的标号是 1 ,2;第2行的两个元素在总区间中对应的标号为 4,5.对于子矩阵(1,1,2,2)就更新两次区间即可
下面就将问题转化为了怎么在一维区间里进行这些操作

线段树记录的信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct SegTree{
int l,r;
int sum,Max,Min;
int delta;
bool lazyd,lazyv;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r;
sum = Max = Min = delta = 0;
lazyd = lazyv = false;
}
int mid(){
return (l+r)>>1;
}
int callen(){
return r - l + 1;
}
}t[N<<2];

其中两个lazy标记比较重要。

lazyd表示该区间上一次是否进行过增值操作,lazyv表示该区间上一次是否进行过设值操作。我的逻辑是,lazyd和lazyv不能同时为true(即上一次的操作肯定是唯一的),但可以同时为false。

对于增值操作,来到目标区间

  1. lazyd = true,说明之前已经进行过增值操作,那么再增,只需要 delta += val;即补上这次的增值
  2. lazyv = true,说明之前进行过设值操作,那么这次增加,其实相当于两次操作合并在一次设值,max+=val,min+=val,sum+=val*len;

对于设值操作,则不需要讨论,因为设值操作的优先级比较高,直接将该区间的标记改为lazyv = true,lazyd = false;另外更新max,min,sum

【要点是,无论如何,在更新时要做充分,对于任何一个区间,任何时刻,都不会lazyv和lazyd同时为true】

另一个容易错的地方是PushDown,自顶向下的更新,就是在这里没有理清逻辑关系,wa了很多次。

一个区间能向下更新,说明它的标记为真,之前有更新信息,这次可以传递过儿子节点

  1. 当前区间lazyv为真
    说明该区间被设值,传递给儿子。但是注意两个儿子的标记,如果儿子中有lazyd标记的话,要消掉,也要把delta = 0;因为设值操作能覆盖掉增值操作。然后设置儿子的lazyv标记为真
  2. 当前区间lazyd为真
    传递给儿子时,要看看儿子的标记。如果儿子lazyd = true,说明之前也是进行增值操作,这次再增,就叠加,delta += val;如果lazyv = true,说明之前被设置,那么现在将增量传递下去,两次合并还是增值,所以保持lazyv不见,但是要更新max,min,sum

至于PushUp,没什么特别,直接向上更新即可,只需要更新max,min,sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1000010
#define INF 0x3f3f3f3f
#define lson(i) ((i)<<1)
#define rson(i) ((i)<<1|1)

int row,col,n;
struct SegTree{
int l,r;
int sum,Max,Min;
int delta;
bool lazyd,lazyv;
SegTree(){}
SegTree(int _l,int _r){
l = _l; r = _r;
sum = Max = Min = delta = 0;
lazyd = lazyv = false;
}
int mid(){
return (l+r)>>1;
}
int callen(){
return r - l + 1;
}
}t[N<<2];

void build(int rt,int a,int b){
t[rt] = SegTree(a,b);
if(a == b) return ;
int mid = t[rt].mid();
build(lson(rt),a,mid);
build(rson(rt),mid+1,b);
}

void PushDown(int rt){
if(!t[rt].lazyd && !t[rt].lazyv) return ;
if(t[rt].lazyd){
t[lson(rt)].Max += t[rt].delta;
t[lson(rt)].Min += t[rt].delta;
t[lson(rt)].sum += t[rt].delta * t[lson(rt)].callen();

t[rson(rt)].Max += t[rt].delta;
t[rson(rt)].Min += t[rt].delta;
t[rson(rt)].sum += t[rt].delta * t[rson(rt)].callen();

if(!t[lson(rt)].lazyv){
t[lson(rt)].lazyd = true;
t[lson(rt)].delta += t[rt].delta;
}

if(!t[rson(rt)].lazyv){
t[rson(rt)].lazyd = true;
t[rson(rt)].delta += t[rt].delta;
}

t[rt].delta = 0; t[rt].lazyd = false;
}
else{
t[lson(rt)].lazyv = t[rson(rt)].lazyv = true;
t[lson(rt)].lazyd = t[rson(rt)].lazyd = false;
t[lson(rt)].delta = t[rson(rt)].delta = 0;

t[lson(rt)].Max = t[lson(rt)].Min = t[rt].Max;
t[lson(rt)].sum = t[lson(rt)].Max * t[lson(rt)].callen();

t[rson(rt)].Max = t[rson(rt)].Min = t[rt].Max;
t[rson(rt)].sum = t[rson(rt)].Max * t[rson(rt)].callen();

t[rt].lazyv = false;
}
}

void PushUp(int rt){
t[rt].Max = max(t[lson(rt)].Max,t[rson(rt)].Max);
t[rt].Min = min(t[lson(rt)].Min,t[rson(rt)].Min);
t[rt].sum = t[lson(rt)].sum + t[rson(rt)].sum;
}

void updata(int rt,int a,int b,int k,int val){
if(t[rt].l == a && t[rt].r == b){
if(k == 1){
t[rt].Max += val; t[rt].Min += val;
t[rt].sum += val*t[rt].callen();
if(t[rt].lazyd)
t[rt].delta += val;
else if(t[rt].lazyv)
t[rt].delta = 0;
else{
t[rt].delta = val; t[rt].lazyd = true;
}
}
else{
t[rt].lazyv = true; t[rt].lazyd = false; t[rt].delta = 0;
t[rt].Max = t[rt].Min = val; t[rt].sum = val*t[rt].callen();
}
return ;
}
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
updata(lson(rt),a,b,k,val);
else if(a > mid)
updata(rson(rt),a,b,k,val);
else{
updata(lson(rt),a,mid,k,val);
updata(rson(rt),mid+1,b,k,val);
}
PushUp(rt);
}

SegTree query(int rt,int a,int b){
if(t[rt].l == a && t[rt].r == b)
return t[rt];
PushDown(rt);
int mid = t[rt].mid();
if(b <= mid)
return query(lson(rt),a,b);
else if(a > mid)
return query(rson(rt),a,b);
else{
SegTree res1 = query(lson(rt),a,mid);
SegTree res2 = query(rson(rt),mid+1,b);
SegTree res;
res.sum = res1.sum + res2.sum;
res.Max = max(res1.Max,res2.Max);
res.Min = min(res1.Min,res2.Min);
return res;
}
}

int main(){
int q; int cas = 0;
while(scanf("%d%d%d",&row,&col,&q)!=EOF){
n = row * col;
build(1,1,n);
while(q--){
int op,x1,y1,x2,y2,val;
scanf("%d",&op);
if(op == 1){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
for(int i = x1; i<=x2; i++){
int a = (i-1)*col+y1;
int b = (i-1)*col+y2;
updata(1,a,b,1,val);
}
}
else if(op == 2){
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&val);
for(int i = x1; i <= x2; i++){
int a = (i-1)*col+y1;
int b = (i-1)*col+y2;
updata(1,a,b,2,val);
}
}
else{
SegTree ans;
ans.sum = 0; ans.Max = -INF; ans.Min = INF;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
for(int i = x1; i <= x2; i++){
int a = (i-1)*col+y1;
int b = (i-1)*col+y2;
SegTree res = query(1,a,b);
ans.Min = min(ans.Min , res.Min);
ans.Max = max(ans.Max , res.Max);
ans.sum += res.sum;
}
printf("%d %d %d\n",ans.sum,ans.Min,ans.Max);
}
}
}
return 0;
}