题目描述
blablabla
样例
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//前缀和求二维数组字矩阵和
int n,m,q;
const int N = 1010;
int arr1[N][N];
int arr2[N][N];
int main(int argc, char** argv) {
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>arr1[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
arr2[i][j] = arr2[i-1][j]+arr2[i][j-1]+arr1[i][j]-arr2[i-1][j-1];
}
}
while(q--){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
int m = arr2[x2][y2] - arr2[x1-1][y2]-arr2[x2][y1-1]+arr2[x1-1][y1-1];
cout<<m<<endl;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla