题目
在一个01矩阵内,选择某个子矩阵取反或输出某点的01值。
分析
可以用二维树状数组解决这个问题,
void add(int x
,int y
,int z
){
while (x
<=n
){
int y1
=y
;
while (y1
<=n
){
c
[x
][y1
]+=z
;
y1
+=(y1
&(-y1
));
}
x
+=(x
&(-x
));
}
}
但是关键是怎么操作 修改后就可以了。
代码
#include <cstdio>
#include <cstring>
using namespace std
;
int n
,c
[1001][1001],t
,m
;
void add(int x
,int y
,int z
){
while (x
<=n
){
int y1
=y
;
while (y1
<=n
){
c
[x
][y1
]+=z
;
y1
+=(y1
&(-y1
));
}
x
+=(x
&(-x
));
}
}
int answ(int x
,int y
){
int ans
=0;
while (x
){
int y1
=y
;
while (y1
){
ans
+=c
[x
][y1
];
y1
-=(y1
&(-y1
));
}
x
-=(x
&(-x
));
}
return ans
;
}
int main(){
scanf("%d",&t
);
while (t
--){
memset(c
,0,sizeof(c
));
scanf("%d%d\n",&n
,&m
);
while (m
--){
char q
; int x
,y
;
scanf("%c%d%d",&q
,&x
,&y
);
if (q
=='C'){
int x1
,y1
;
scanf("%d%d\n",&x1
,&y1
);
add(x
,y
,1);
add(x
,y1
+1,-1);
add(x1
+1,y
,-1);
add(x1
+1,y1
+1,1);
}
else printf("%d\n",answ(x
,y
)&1),getchar();
}
putchar('\n');
}
return 0;
}
转载请注明原文地址: https://www.6miu.com/read-3850120.html