蓝桥杯 17110抓娃娃

问题描述

小明拿了 n 条线段练习抓娃娃。他将所有线段铺在数轴上,第 i 条线段的左端点在 li,右端点在 ri​。小明用 m 个区间去框这些线段,第 i个区间的范围是 [Li​, Ri​]。如果一个线段有 至少一半 的长度被包含在某个区间内,则将其视为被这个区间框住。请计算出每个区间框住了多少个线段?

输入格式

输入共 n+m+1 行。

第一行为两个正整数 n, m。

后面 n 行,每行两个整数 li​, ri​。

后面 m 行,每行两个整数Li​, Ri​。

输出格式

输出共 m 行,每行一个整数。

样例输入

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

样例输出

3
2

评测用例规模与约定

对于 20%20% 的数据,保证 n,m≤10^{3}

对于 100%100% 的数据,保证 n,m≤10^{5},li​<ri​,0<li,ri,Li,Ri≤10^{6},max⁡{ri−li}≤min⁡{Ri−Li}.

运行限制

语言最大运行时间最大运行内存
C++1s256M
C1s256M
Java3s256M
Python33s256M
PyPy33s256M
Go3s256M
JavaScript3s256M

 

首先题目保证了 max{ri​−li​}≤min{Ri​−Li​},那么如果某个区间包含了某个线段,则该区间一定包含了这个线段的中点。

我们就可以在输入 li​,ri​ 的时候,标记其中点 (mp[(l+r)/2]++),再做一遍前缀和,最后查询时 [Li​,Ri​] 这个区间的和就是答案。

注意:

有可能会出现中点的位置是个小数这种情况,所以我们不妨把所有坐标都 ×2 (不要忘记数组大小也要开两倍),以避免上述情况的发生。

 

#include<iostream>
using namespace std;const int N = 2e6+10;
int n, m;  //n条线段  m个区间
int mp[N];int main()
{cin>>n>>m;int l, r;for(int i=1; i<=n; ++i){cin>>l>>r;mp[l+r]++;  //记录每条线段中点的位置 }for(int i=1; i<N; ++i){mp[i] += mp[i-1];}for(int i=1; i<=m; ++i){cin>>l>>r;l *= 2;r *= 2;//一段区间包含了多少个中点就覆盖了多少条线段 cout<<mp[r] - mp[l-1]<<endl;  //l-1:线段的中点恰好在 L 上 }return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/33901.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

linux ptrace 图文详解(二) PTRACE_TRACEME 跟踪程序

目录 一、基础介绍 二、PTRACE_TRACE 实现原理 三、代码实现 四、总结 &#xff08;代码&#xff1a;linux 6.3.1&#xff0c;架构&#xff1a;arm64&#xff09; One look is worth a thousand words. —— Tess Flanders 一、基础介绍 GDB&#xff08;GNU Debugger&…

记录致远OA服务器硬盘升级过程

前言 日常使用中OA系统突然卡死&#xff0c;刷新访问进不去系统&#xff0c;ping服务器地址正常&#xff0c;立马登录服务器检查&#xff0c;一看磁盘爆了。 我大脑直接萎缩了&#xff0c;谁家OA系统配400G的空间啊&#xff0c;过我手的服务器没有50也是30台&#xff0c;还是…

电网电压暂态扰动机理与工业设备抗失压防护策略研究

什么是晃电&#xff1f; 国标GB/T 30137-2013 中定义:工频电压方均根值突然降至额定值的90%~10%&#xff0c;持续时间为10ms~1min后恢复正常的现象。Acrel8757V 晃电的原因 1.系统侧因素 短路故障&#xff1a;雷击、线路接地、设备误碰等导致电网短路&#xff0c;故障点电压…

Linux监控网络状态

一、基本介绍 1、基本语法 netstat [选项] 2、常用选项 选项 说明 -a 显示所有连接和监听的套接字&#xff08;包括TCP、UDP&#xff09;。 -t 显示 TCP 连接。 -u 显示 UDP 连接。 -l 显示正在监听的套接字&#xff08;server端&#xff09;。 -n 显示数字格式的…

UE5以插件的形式加载第三方库

之前在UE中加载第三方库的形式是以静态或者动态链接的形式加载但是不太容易复用。就想着能不能以插件的形式加载第三方库&#xff0c;这样直接把插件打包发行就可以复用了&#xff0c;之前也找过相应的教程但是很难找到比较简单易懂的教程&#xff0c;要么是比较复杂&#xff0…

Go执行当前package下的所有方法

需求&#xff1a;需要一个文件一个定时任务方法&#xff0c;当项目初始化完毕后&#xff0c;自动加载并执行这些定时任务方法 项目目录架构 main.go 初始化 package mainimport ("sql_demo/schedule" )func main() {/***** 其他初始化完毕后的操作**/// 定时任务sc…

AnyAnomaly: 基于大型视觉语言模型的零样本可定制视频异常检测

文章目录 速览摘要1. 引言2. 相关工作视频异常检测大型视觉语言模型&#xff08;LVLMs&#xff09; 3. 方法3.1. 总览3.2. 关键帧选择模块3.3. 上下文生成基于 WinCLIP 的注意力机制网格图像生成 3.4. 异常检测提示词设计异常评分 4. 实验4.1. 数据集4.2. 评估标准4.3. 结果4.4…

【AWS入门】2025 AWS亚马逊云科技账户注册指南

【AWS入门】2025 AWS亚马逊云科技账户注册指南 A Guide To Register a New account on AWS By JacksonML 0. AWS亚马逊云科技简介 Amazon Web Service(AWS) 即亚马逊云科技&#xff0c;其在全球Cloud Computing(云计算)市场占有最为重要的地位。 AWS连续13年被Gartner评为…

Spring 中 SmartInitializingSingleton 的作用和示例

一、 接口定义 SmartInitializingSingleton 是 Spring 框架提供的一个 单例 Bean 全局初始化回调接口&#xff0c;用于在 所有非延迟单例 Bean 初始化完成后 执行自定义逻辑。 核心方法&#xff1a; public interface SmartInitializingSingleton {void afterSingletonsInsta…

element tree树形结构默认展开全部

背景&#xff1a; el-tree树形结构&#xff0c;默认展开全部&#xff0c;使用属性default-expand-all【是否默认展开所有节点】&#xff1b;默认展开一级&#xff0c;设置default-expanded-keys【默认展开的节点的 key 的数组】属性值为数组。 因为我这里的数据第一级是四川【省…

大数据-spark3.5安装部署之local模式

spark&#xff0c;一个数据处理框架和计算引擎。 下载 local模式即本地模式&#xff0c;就是不需要任何其他节点资源就可以在本地执行spark代码的环境。用于练习演示。 上传解压 使用PortX将文件上传至/opt 进入/opt目录&#xff0c;创建目录module&#xff0c;解压文件至/o…

Discuz建站教程之论坛头部logo跳转链接怎么修改?

在修改头部logo跳转链接前&#xff0c;我们需要知道对应代码在哪个文件目录&#xff0c;进入宝塔或是服务器&#xff0c;找到文件&#xff1a;\template\default\common\header.htm&#xff0c;编辑器打开&#xff0c;搜索以下代码&#xff0c;大概在135行 <a href"{i…

【FreeRTOS】FreeRTOS操作系统在嵌入式单片机上裸机移植

目录 一 RTOS概述 二 FreeRTOS移植 三 FreeRTOS使用 四 附录 一 RTOS概述 先了解一些基础概念,以下内容摘自FreeRTOS官网(FreeRTOS™ - FreeRTOS™): 【1】RTOS基础知识 实时操作系统 (RTOS) 是一种体积小巧、确定性强的计算机操作系统。 RTOS 通常用于需要在严格时间限…

编译支持 RKmpp 和 RGA 的 ffmpeg 源码

一、前言 RK3588 支持VPU硬件解码&#xff0c;需要rkmpp进行调用&#xff1b;支持2D图像加速&#xff0c;需要 RGA 进行调用。 这两个库均能通过 ffmpeg-rockchip 进行间接调用&#xff0c;编译时需要开启对应的功能。 二、依赖安装 编译ffmpeg前需要编译 rkmpp 和 RGA&#xf…

深度学习基础:线性代数本质2——线性组合、张成的空间与基

目录 一、线性组合 1. 用一个有趣的角度看向量坐标 2. 如果我们选择不同的基向量会怎样&#xff1f; 3. 线性组合 4. 张成的空间 ① 二维向量的张成的空间 ② 三维向量的张成的空间​编辑 5.线性相关 6.线性无关 7. 基的定义 一、线性组合 1. 用一个有趣的角度看向量坐…

openharmony5.0中HDF驱动框架源码梳理-服务管理接口

要想大概了解一个公司&#xff0c;我们可能只需要知道它的运行逻辑即可&#xff0c;例如我们只需要知道它有财务有研发有运营等&#xff0c;财务报销、研发负责产品等即可&#xff0c;但是如果想深入具体的了解的话我们就要了解都有什么部门(对象)、各部门都包含哪些职责(对象方…

Go语言环境搭建并执行第一个Go程序

目录 一、Windows环境搭建 二、vscode安装插件 三、运行第一个go程序 一、Windows环境搭建 下载Go&#xff1a;All releases - The Go Programming Language 这里是Windows搭建&#xff0c;选择的是windows-amd64.msi&#xff0c;也可以选择zip直接解压缩到指定目录 选择msi…

Netty基础—4.NIO的使用简介一

大纲 1.Buffer缓冲区 2.Channel通道 3.BIO编程 4.伪异步IO编程 5.改造程序以支持长连接 6.NIO三大核心组件 7.NIO服务端的创建流程 8.NIO客户端的创建流程 9.NIO优点总结 10.NIO问题总结 1.Buffer缓冲区 (1)Buffer缓冲区的作用 (2)Buffer缓冲区的4个核心概念 (3)使…

linux 命令 tail

tail 是 Linux 中用于查看文件末尾内容的命令&#xff0c;常用于日志监控和大文件快速浏览。以下是其核心用法及常见选项&#xff1a; 基本语法 tail [选项] 文件名 常用选项 显示末尾行数 -n <行数> 或 --lines<行数> 指定显示文件的最后若干行&#xff08;…

网络华为HCIA+HCIP数据链路层协议-以太网协议

以太网协议 以太网是当今现有局域网(Local Area Network,LAN)采用的最通用的通信协议标准&#xff0c;该标准定义了在局域网中采用的电缆类型和信号处理方法。以太网是建立在CSMA/CD(Carrier Sense Multiple Access/Collision Detection,载波监听多路访问/冲突检测)机制上的广…