成都网站建设哪个好,网站建站网站设计公司,重庆网站建设cq600,wordpress qtan题目#xff1a;
给出一个 nn 行 mm 列的矩阵#xff0c;矩阵的每个位置有一个非负整数 a[i][j]#xff0c;有 qq 次询问#xff0c;每次询问求一个左上角为 (a,b)#xff0c;右下角为 (c,d) 的子矩阵的所有数之和。
输入格式
第一行两个整数 n,m#xff0c;表示矩阵的…题目
给出一个 nn 行 mm 列的矩阵矩阵的每个位置有一个非负整数 a[i][j]有 qq 次询问每次询问求一个左上角为 (a,b)右下角为 (c,d) 的子矩阵的所有数之和。
输入格式
第一行两个整数 n,m表示矩阵的行和列的大小。
接下来 nn 行每行 m 个整数为矩阵内容。
接下来一行为一个整数 q 表示询问次数。
接下来 q 行每行 44 个整数 a,b,c,d含义见题面。
输出格式
共 q 行第 i 行为第 i个询问的答案。
数据范围 n×m≤100,000a[i][j]≤1000q≤100,0001≤a≤c≤n1≤b≤d≤m。n×m≤100,000a[i][j]≤1000q≤100,000 1≤a≤c≤n1 \le b \le d \le m。n×m≤100,000a[i][j]≤1000q≤100,0001≤a≤c≤n1≤b≤d≤m。
输出时每行末尾的多余空格不影响答案正确性
要求使用「文件输入输出」的方式解题输入文件为 sum.in输出文件为 sum.out
样例输入
3 5 1 2 3 4 5 3 2 1 4 7 2 4 2 1 2 3 1 1 3 5 2 2 3 3 1 1 3 3
样例输出
43 9 20
分析
1、先打表计算二维前缀和再进行之后每次的查询。 2、需要使用数据结构vector存储数据。因为n×m≤100,000n×m≤100,000n×m≤100,000,要是开二维数组会爆所以用vector容器存数据。 如图所示假设要求S的话可以用最大的矩形和减去S1S2再减去S1S3最后再加上S1即可。
AC代码
#includestdio.h
#includestring.h
#includealgorithm
#includeiostream
#includevector
using namespace std;
const int M1e510;
const int inf0x3f3f3f3f;
int n,m,k;
vectorintmp[M];
int main(){freopen(sum.in, r, stdin);freopen(sum.out, w, stdout);scanf(%d%d,n,m);for(int i1;in;i){mp[i].push_back(0);for(int j1;jm;j){int x;scanf(%d,x);mp[i].push_back(x);}}for(int i0;im;i)mp[0].push_back(0);for(int i1;in;i)for(int j1;jm;j)mp[i][j]mp[i-1][j]mp[i][j-1]-mp[i-1][j-1];scanf(%d,k);while(k--){int a,b,c,d;scanf(%d%d%d%d,a,b,c,d);int ansmp[c][d]mp[a-1][b-1]-mp[a-1][d]-mp[c][b-1];printf(%d\n,ans);}
}
/**
5 5
636 848 745 281 87
895 796 850 713 242
16 128 270 845 922
338 690 30 327 273
779 154 192 656 64
5
2 1 4 2
1 1 1 1
2 1 4 2
2 1 4 2
2 1 2 3
*/
