#二维树状数组#poj 2155 Matrix

xiaoxiao2021-03-01  5

题目

在一个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

最新回复(0)