Description
Given a matrix, the elements of which are all integer number from 0 to 50, you are required to evaluate the square sum of its specified sub-matrix.
Input
The first line of the input contains a single integer T (1 <= T <= 5), the number of test cases.
For each test case, the first line contains two integers m and n (1
<= m, n <= 500), which are the row and column sizes of the matrix,
respectively. The next m lines with n numbers each gives the elements
of the matrix.
The next line contains a single integer N (1
<= N <= 100,000), the number of queries. The next N lines give one
query on each line, with four integers r1, c1, r2, c2 (1 <= r1 <=
r2 <= m, 1 <= c1 <= c2 <= n), which are the indices of the
upper-left corner and lower-right corner of the sub-matrix in question.
Output
For each test case, first print the number of the test case, then N
lines with one number on each line, the required square sum. Refer to
the sample output for details.
Sample Input
2
2 3
1 2 3
4 5 6
2
1 1 2 2
1 3 2 3
3 3
4 2 3
2 5 1
7 9 2
1
1 1 3 3
Sample Output
Case 1:
46
45
Case 2:
193
题意：
给一个n*m矩阵 下表（1,1)~~~(n,m)
给两个点做对角线 求中间矩阵的值
朴素算法也可以过 但是这个在不断输入的同时也将值存在数组中 查询更快
#include <iostream>
#include <string.h>
#include <stdio.h> using namespace std; int main()
{
int t;
int n,m;
int k;
int tt,x1,x2,y1,y2;
int num;
int map[505][505];
scanf("%d",&t);
for(num=1;num<=t;num++)
{
scanf("%d%d",&n,&m);
memset(map,0,sizeof(map));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&k);
map[i][j]=k*k+map[i-1][j]+map[i][j-1]-map[i-1][j-1];
}
}
printf("Case %d:\n",num);
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int ans=map[x1-1][y1-1]+map[x2][y2]-map[x1-1][y2]-map[x2][y1-1];
printf("%d\n",ans); }
}
return 0;
}
#include<iostream>
#include <string.h>
#include <stdio.h>using namespace std;int a[ 510 ][ 510 ];
int sum[ 510 ][ 510 ];int main()
{
int t,n,m,tt;
int ss;
int k;
int r1,c1,r2,c2;
scanf("%d",&t);
for(k=1; k<=t; k++)
{
scanf("%d%d",&n,&m);
memset(sum,0,sizeof(sum));
for(int i=1; i<=n; i++)
{
ss = 0;
for(int j=1; j<=m; j++)
{
scanf("%d",&a[i][j]);
ss += a[i][j] * a[i][j];
sum[i][j] = sum[ i - 1 ][ j ] + ss;
}
}
printf("Case %d:\n",k);
scanf("%d",&tt);
while(tt--)
{
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
printf("%d\n",sum[ r2 ][ c2 ] - sum[ r1-1 ][ c2 ] - sum[ r2 ][ c1 - 1 ] + sum[ r1 - 1 ][ c1 - 1 ] );
}
}
return 0;}
