[luogu] P3801 红色的幻想乡 树状数组

前言

传送门 :

思路

观察题目之后,如果将矩阵看成一个 01 01 01矩阵,不难发现

其实最终答案 就是求 二维前缀和

只是对于每次操作都是 行列的 取反操作

想到前缀和我们就联想可以使用树状数组维护,

因此我么可以创立两个树状数组,从而进行维护区间的值

下面的操作就是二维前缀和的操作了

MyCode

const int N  = 1e5+10;
int Tx[N],Ty[N];
int n,m,q;
int stx[N],sty[N];

int lowbit(int x){
	return x & -x;
	
}
void add(int * C,int x,int k){
	for(int i = x; i >n>>m>>q;
	for(int i = 1;i>op;
		
		if(op == 1){
			cin>>a>>b;
			if(!stx[a]){
				stx[a] = 1;
				add(Tx,a,1);
			}else{
				stx[a] = 0 ;
				add(Tx,a,-1);
			}
			
			if(!sty[b]){
				sty[b] = 1;
				add(Ty,b,1);
			}else{
				sty[b] = 0;
				add(Ty,b,-1);
			}
		}else{
			cin>>x1>>y1>>x2>>y2;
			int s1 = query(Tx,x2)  - query(Tx,x1-1);
			int s2 = query(Ty,y2)  - query(Ty,y1-1);
			
			cout