当前位置: 开发笔记 > 程序员 > 正文

二维前缀和

作者：happy雨之泪 | 来源：互联网 | 2023-05-17 22:02

题目链接：https:ac.nowcoder.comacmproblem21862海啸题目描述有一个沿海地区，可以看作有n行m列的城市，第i行第j列的城市海拔为h[i][j]。由于

题目链接：https://ac.nowcoder.com/acm/problem/21862

海啸

题目描述

有一个沿海地区，可以看作有n行m列的城市，第i行第j列的城市海拔为h[i][j]。
由于沿海，所以这个地区经常会发生海啸。
海啸发生时，部分城市会被淹没，具体来说，海水高度会达到d，因此海拔低于d的城市都会被淹没。
现在有q次询问，每次问你一个矩形区域中，有多少城市不会被淹没。

输入描述:

第一行三个整数n,m,d，具体含义见题目描述。
接下来n行，每行m个整数，其中第i行第j列的整数为h[i][j]，具体含义见题目描述。
第n+2行一个整数q，表示询问数。
接下来q行，每行四个整数a,b,x,y，
表示询问从第a行第b列到第x行第y列的矩形地区中，有多少地区不会被淹没。
即有多少个i,j，满足 a<=i<=x,b<=j<=y，且 h[i][j]>d。

输出描述:

共q行，第i行一个整数，表示第i个询问的答案。

输入

3 3 3
1 2 3
2 1 5
4 3 2
2
1 2 2 3
2 1 3 3

输出

2
3

备注:

1<=n*m<=10^6

1<=q<=10^5

0<=d,h[i][j]<=10^9

1<=a<=x<=n,1<=b<=y<=m

1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 using namespace std;
10 #define ll long long
11 const int inf=99999999;
12 const int mod=1e9+7;
13 const int maxn=1e6+2;
14 int main()
15 {
16 ios::sync_with_stdio(false);
17 int n,m,d;
18 cin>>n>>m>>d;
19 int sum[n+1][m+1];
20 memset(sum,0,sizeof(sum));
21 int num;
22 //根据题意导入二维数组
23 for(int i=1;i<=n;i++)
24 {
25 for(int j=1;j<=m;j++)
26 {
27 cin>>num;
28 if(num29 sum[i][j]=0;
30 else
31 sum[i][j]=1;
32 }
33 }
34 //积二维前缀和
35 for(int i=1;i<=n;i++)
36 {
37 for(int j=1;j<=m;j++)
38 {
39 sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
40 }
41 }
42 int op;
43 cin>>op;
44 int x1,y1,x2,y2;
45 while(op--)
46 {
47 cin>>x1>>y1>>x2>>y2;
48 cout<49 }
50 return 0;
51 }

https

推荐阅读

https
Python 实现字符串双拆分并转换为矩阵

本文介绍如何使用 Python 将一个字符串按照指定的行和元素分隔符进行两次拆分，最终将字符串转换为矩阵形式。通过两种不同的方法实现这一功能：一种是使用循环与 split() 方法，另一种是利用列表推导式。 ... [详细]

蜡笔小新 2024-12-28 12:15:45
https
深入理解LOAM：激光雷达里程计与建图算法

本文基于对相关论文和开源代码的研究，详细介绍了LOAM（激光雷达里程计与建图）的工作原理，并对其关键技术进行了分析。 ... [详细]

蜡笔小新 2024-12-28 11:38:00
https
Java 中 Writer flush()方法，示例

Java 中 Writer flush()方法，示例 ... [详细]

蜡笔小新 2024-12-28 06:41:52
编程
技术分享：从动态网站提取站点密钥的解决方案

本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]

蜡笔小新 2024-12-28 04:11:47
程序员
程序员思维：深入解析与应用

本文探讨了如何像程序员一样思考，强调了将复杂问题分解为更小模块的重要性，并讨论了如何通过妥善管理和复用已有代码来提高编程效率。 ... [详细]

蜡笔小新 2024-12-28 01:48:10
编程
python的交互模式怎么输出名文汉字[python常见问题]

在命令行模式下敲命令python，就看到类似如下的一堆文本输出，然后就进入到Python交互模式，它的提示符是>>>，此时我们可以使用print() ... [详细]

蜡笔小新 2024-12-27 21:32:05
编程
火星商店问题：线段树分治与持久化Trie树的应用

本题涉及编号为1至n的火星商店，每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品，以及查询某段时间内某些商店中所有商品（含永久商品）与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]

蜡笔小新 2024-12-27 21:23:11
编程
Java 中的 BigDecimal pow()方法，示例

Java 中的 BigDecimal pow()方法，示例 ... [详细]

蜡笔小新 2024-12-27 20:54:03
编程
汇编语言高级特性总结

本文总结了汇编语言中第五至第八章的关键知识点，涵盖间接寻址、指令格式、安全编程空间、逻辑运算指令及数据重复定义等内容。通过详细解析这些内容，帮助读者更好地理解和应用汇编语言的高级特性。 ... [详细]

蜡笔小新 2024-12-27 19:52:28
编程
FastJSON解析与数据提取技巧

探讨如何高效使用FastJSON进行JSON数据解析，特别是从复杂嵌套结构中提取特定字段值的方法。 ... [详细]

蜡笔小新 2024-12-27 19:49:07
编译
网络链路质量监控：Smokeping部署与配置

本文详细介绍了如何在Linux系统上安装和配置Smokeping，以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装，确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]

蜡笔小新 2024-12-27 19:31:05
编译
Maven多模块项目管理最佳实践

本文详细介绍了如何使用Maven高效管理多模块项目，涵盖项目结构设计、依赖管理和构建优化等方面。通过具体的实例和配置说明，帮助开发者更好地理解和应用Maven在复杂项目中的优势。 ... [详细]

蜡笔小新 2024-12-27 19:29:15
编译
路由器配置与网络地址转换

本文介绍了如何在具备多个IP地址的FTP服务器环境中，通过动态地址端口复用和地址转换技术优化网络配置。重点讨论了2Mb/s DDN专线连接、Cisco 2611路由器及内部网络地址规划。 ... [详细]

蜡笔小新 2024-12-27 18:25:35
编译
深入理解Cookie与Session会话管理

本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息，以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制，解释其原理及应用场景。 ... [详细]

蜡笔小新 2024-12-27 18:20:43
编译
解决 Python 项目中 setuptools_rust 模块缺失问题

本文介绍了在安装或运行 Python 项目时遇到的 'ModuleNotFoundError: No module named setuptools_rust' 错误，并提供了解决方案。 ... [详细]

蜡笔小新 2024-12-27 18:06:18

happy雨之泪

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章