796. 子矩阵的和

电玩女神 2023-09-30 11:57 13阅读 0赞

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数 x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入格式  
第一行包含三个整数 n，m，q。

接下来 n 行，每行包含 m 个整数，表示整数矩阵。

接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式  
共 q 行，每行输出一个询问的结果。

数据范围  
1≤n,m≤1000,  
1≤q≤200000,  
1≤x1≤x2≤n,  
1≤y1≤y2≤m,  
−1000≤矩阵内元素的值≤1000

输入样例：
    3 4 3
    1 7 2 4
    3 6 2 8
    2 1 2 3
    1 1 2 2
    2 1 3 4
    1 3 3 4
    输出样例：
    17
    27
    21

难度：简单  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16 1]

#include<iostream>
    using namespace std;
    
    const int N=1010;
    int n,m,q;
    int a[N][N],s[N][N];
    
    int main(){
        
        scanf("%d%d%d",&n,&m,&q);
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                scanf("%d",&a[i][j]);
            }
        }
        
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                //求前缀和
                s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
            }
        }
        
        while(q--){
        
            int x1,y1,x2,y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
        }
        return 0;
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/8e27ce41389e4b5c90049ada15f2d325.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiD5a-75YyX6YeM,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/8fe83fda77ab41ee9af5189f03e4587a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiD5a-75YyX6YeM,size_20,color_FFFFFF,t_70,g_se,x_16