题目

情人节到了，小芳和小明手牵手，打算过一个完美的情人节，但是小刚偏偏也来了，当了一个明晃晃的电灯泡，小明很尴尬，就和小刚说，我交给你个任务，你完成了我俩就带你玩，否则你就回家吧。小刚很有当单身狗的觉悟，他坚决不想让小明过好情人节，同为单身狗的你能帮帮他吗？现在有一个n×n（1<=n<=1000）的格子，每一个格子都有一个电灯泡，可能是亮的，也可能是灭的（1代表亮， 0代表灭），现在有两种操作，一种是给你一个坐标，对于那个坐标上的灯泡，如果他是亮的，那么熄灭他，反之如果他是灭的，那么打开它。第二种操作是给你两个坐标，第一个坐标代表一个子矩阵的左上角，另一个坐标是右下角，请你求出当前子矩阵中有多少个灯泡是亮着的。燥起来吧！！！单身狗们！！！！

思路

c[i][j]记录以(1,1)为左上角坐标，(i,j)为右下角坐标的子矩阵中所有亮着的电灯泡数量。

操作一：

点亮：0->1 数目+1

update(x1,y1,1);a[x1][y1]=1;

熄灭：1->0 数目-1

update(x1,y1,-1);a[x1][y1]=0;

操作二

求(x1,y1)到(x2,y2)矩阵的数目，即

cout<<getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1)<<endl;

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&(-x))
int n,m;
const int maxn=1005;
int a[maxn][maxn];
int c[maxn][maxn];

void update(int x,int y,int z)
{
	for(int i=x;i<=n;i+=lowbit(i))
		for(int j=y;j<=n;j+=lowbit(j))
			c[i][j]+=z;
}
int getsum(int x,int y)
{
	int sum=0;
	for(int i=x;i>0;i-=lowbit(i))
		for(int j=y;j>0;j-=lowbit(j))
			sum+=c[i][j];
	return sum;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>a[i][j];
			if(a[i][j]) update(i,j,1);
		}
	}
	
	while(m--)
	{
		int f;
		cin>>f;
		if(f==1)
		{
			int x1,y1;
			cin>>x1>>y1;
			if(a[x1][y1]) 
			{
				update(x1,y1,-1);	
				a[x1][y1]=0;
			}
			else
			{
				update(x1,y1,1);
				a[x1][y1]=1;
			}
		}
		else if(f==2)
		{
			int x1,y1,x2,y2;
			cin>>x1>>y1>>x2>>y2;
			cout<<getsum(x2,y2)-getsum(x2,y1-1)-getsum(x1-1,y2)+getsum(x1-1,y1-1)<<endl;
		}
	}
	return 0;
}