A335.前缀和2 思路+代码

思路：
这道题可以通过前缀和来做。
重点：二维数组的前缀和要用一维数组记录
前缀和数组rc第i行第j列的下标是rc[(i-1)×m+j]

代码：

#include <iostream>
#include <cstdio>

using namespace std;

int n,m,q;
int num[101][101];
int rc[1000000];
int tp;
int a,b,x,y;

int main()
{

	scanf("%d %d %d",&n,&m,&q);
	
	for (int i=1; i<=n; i++)
	{
		
		for (int j=1; j<=n; j++)
		{
			
			scanf("%d",&tp);
			
			rc[(i-1)*m+j]=rc[(i-1)*m+j-1]+tp;
			
		}
		
	}
	
	for (int i=1; i<=q; i++)
	{
		
		scanf("%d %d %d %d",&a,&b,&x,&y);
		
		int sum=rc[x*m];
		
		for (int j=a; j<=x; j++)
		{
			
			for (int k=1; k<=m; k++)
			{
				
				if (k<min(b,y) || k>max(b,y)) sum=sum-rc[(j-1)*m+k]+rc[(j-1)*m+k-1];
				
			}
			
		}
		
		printf("%d\n",sum);
		
	}

	return 0;

}