当前位置: 首页 > news >正文

1400*B. Karen and Coffee

Examples

input

3 2 4
91 94
92 97
97 99
92 94
93 97
95 96
90 100

output

3
3
0
4

input

2 1 1
1 1
200000 200000
90 100

output

0

 解析:

        题意为,给你多个区间(会有重叠),每个区间的每个值都会为这个值累加 1。再给一些查询区间,问这个区间有多少个数满足,其累加值大于k。

        数据量2e5,为O(NlogN)的复杂度。

        两重遍历肯定超时,所以要把单次查询的复杂度降低为 logN,所以可以树状数组。

        开始差分记录每个点的累加值,遍历将大于累加值大于等于 k,的点放入树状数组,然后每次查询直接 logN 获取查询区间的满足题意的个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int n,k,q,a[N],c[N],x,y,p[N];
int lowbit(int x){return x&-x;
}
void add(int x){for(int i=x;i<=2e5;i+=lowbit(i)) p[i]+=1;
}
int sum(int x,int k){int ans=0;for(int i=y;i;i-=lowbit(i)) ans+=p[i];for(int i=x-1;i;i-=lowbit(i)) ans-=p[i];return ans;
}
int main(){scanf("%d%d%d",&n,&k,&q);for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);c[x]+=1;	//差分统计每个区间的增加 c[y+1]-=1;}for(int i=1;i<=2e5;i++){a[i]=a[i-1]+c[i];if(a[i]>=k) add(i);		//如果某个点的累计数大于 k,则加入树状数组 }while(q--){scanf("%d%d",&x,&y);printf("%d\n",sum(x,y));	//查询 }return 0;
}

相关文章:

1400*B. Karen and Coffee

Examples input 3 2 4 91 94 92 97 97 99 92 94 93 97 95 96 90 100 output 3 3 0 4 input 2 1 1 1 1 200000 200000 90 100 output 0 解析&#xff1a; 题意为&#xff0c;给你多个区间&#xff08;会有重叠&#xff09;&#xff0c;每个区间的每个值都会为这个值累加…...

【业务功能篇54】Springboot项目常用工具类:HTTP状态码/客户端request

状态码常量类 /*** 返回状态码**/ public class HttpStatus {/*** 操作成功*/public static final int SUCCESS 200;/*** 对象创建成功*/public static final int CREATED 201;/*** 请求已经被接受*/public static final int ACCEPTED 202;/*** 操作已经执行成功&#xff0…...

Fine Logic

登录—专业IT笔试面试备考平台_牛客网 题目大意&#xff1a;有n个数分别为1~n&#xff0c;有m个数值对(u,v)表示u要排在v左边&#xff0c;问至少要多少个排列才能满足所有数值对至少一次 2<n<1e6;1<m<1e6 思路&#xff1a;如果数值对中要求u在v左边&#xff0c;…...

Neo4j图数据基本操作

Neo4j 文章目录 Neo4jCQL结点和关系增删改查匹配语句 根据标签匹配节点根据标签和属性匹配节点删除导入数据目前的问题菜谱解决的问题 命令行窗口 neo4j.bat console 导入rdf格式的文件 :GET /rdf/ping CALL n10s.graphconfig.init(); //初始化 call n10s.rdf.import.fetch(&q…...

前端JavaScript面试100问(中)

31、http 的理解 ? HTTP 协议是超文本传输协议&#xff0c;是客户端浏览器或其他程序“请求”与 Web 服务器响应之间的应用层通信协议。HTTPS主要是由HTTPSSL构建的可进行加密传输、身份认证的一种安全通信通道。32、http 和 https 的区别 ? 1、https协议需要到ca申请证书&…...

Docker 安全及日志管理与https部署

容器的安全性问题的根源在于容器和宿主机共享内核。如果容器里的应用导致Linux内核崩溃&#xff0c;那么整个系统可能都会崩溃。与虚拟机是不同的&#xff0c;虚拟机并没有与主机共享内核&#xff0c;虚拟机崩溃一般不会导致宿主机崩溃。 Docker 容器与虚拟机的区别 虚拟机通…...

2.3 HLSL常用函数

一、函数介绍 函数图像参考网站&#xff1a;Graphtoy 1.基本数学运算 函数 含义 示例图 min(a,b) 返回a、b中较小的数值 mul(a,b) 两数相乘用于矩阵计算 max(a,b) 返回a、b中较大的数值 abs(a) 返回a的绝对值 round(x) 返回与x最近的整数 sqrt(x) 返回x的…...

互联网的发展

概述 互联网是现代社会中举足轻重的一个领域&#xff0c;它的发展对于人类的生活和工作方式产生了深远的影响。互联网的发展经历了几个阶段&#xff0c;从初创阶段到如今的高度普及和深入应用&#xff0c;本文将详细介绍互联网的发展状况。 第一阶段&#xff1a;互联网的起源…...

STM32 CAN通讯实验程序

目录 STM32 CAN通讯实验 CAN硬件原理图 CAN外设原理图 TJA1050T硬件描述 实验线路图 回环实验 CAN头文件配置 CAN_GPIO_Config初始化 CAN初始化结构体 CAN筛选器结构体 接收中断优先级配置 接收中断函数 main文件 实验现象 补充 STM32 CAN通讯实验 CAN硬件原理图…...

Python代码片段之Django静态文件URL的配置

首先要说明这段python代码并不完整&#xff0c;而且我也没有做过测试&#xff0c;只是我在工作时参考了其中的一些个方法。这是我在找python相关源码资料里看到的一段代码&#xff0c;是Django静态文件URL配置代码片段2&#xff0c;代码中有些方法还是挺技巧的&#xff0c;做其…...

基于飞桨paddle的极简方案构建手写数字识别模型测试代码

基于飞桨paddle的极简方案构建手写数字识别模型测试代码 原始测试图片为255X252的图片 因为是极简方案采用的是线性回归模型&#xff0c;所以预测结果数字不一致 本次预测的数字是 [[3]] 测试结果&#xff1a; PS E:\project\python> & D:/Python39/python.exe e:/pro…...

soft ip与hard ip

ip分soft和hard两种&#xff0c;soft就是纯代码&#xff0c;买过来要自己综合自己pr。hard ip如mem和analog与工艺有关。 mem的lib和lef是memory compiler产生的&#xff0c;基于bitcell&#xff0c;是foundry给的。 我正在「拾陆楼」和朋友们讨论有趣的话题&#xff0c;你⼀起…...

MyBatisPlus从入门到精通-2

接着上一讲的Mp的分页功能 下面我们讲解条件查询功能和其他功能 解决一下日志输出和banner问题 每次卞就会输出这些日志 很不美观&#xff0c;现在我们关闭一下 这样建个xml&#xff0c;文件名为logback.xml 文件内容改成这样 配置了logback但是里面什么都没写就不会说有日…...

AI面试官:Asp.Net 中使用Log4Net (一)

AI面试官&#xff1a;Asp.Net 中使用Log4Net (一) 当面试涉及到使用log4net日志记录框架的相关问题时&#xff0c;通常会聚焦在如何在.NET或.NET Core应用程序中集成和使用log4net。以下是一些关于log4net的面试题目&#xff0c;以及相应的解答、案例和代码&#xff1a; 文章目…...

Selenium自动化元素定位方式与浏览器测试脚本

Selenium八大元素定位方法 Selenium可以驱动浏览器完成各种操作&#xff0c;比如模拟点击等。要想操作一个元素&#xff0c;首先应该识别这个元素。人有各种的特征&#xff08;属性&#xff09;&#xff0c;我们可以通过其特征找到人&#xff0c;如通过身份证号、姓名、家庭住…...

人机交互与人机混合智能的区别

人机交互和人机融合智能是两个相关但不完全相同的概念&#xff1a; 人机交互是指人与计算机之间的信息交流和互动过程。它关注的是如何设计和实现用户友好的界面&#xff0c;以便人们能够方便、高效地与计算机进行沟通和操作。人机交互通常强调用户体验和界面设计&#xff0c;旨…...

【项目】轻量级HTTP服务器

文章目录 一、项目介绍二、前置知识2.1 URI、URL、URN2.2 CGI2.2.1 CGI的概念2.2.2 CGI模式的实现2.2.3 CGI的意义 三、项目设计3.1 日志的编写3.2 套接字编写3.3 HTTP服务器实现3.4 HTTP请求与响应结构3.5 EndPoint类的实现3.5.1 EndPoint的基本逻辑3.5.2 读取请求3.5.3 构建响…...

sketch如何在线打开?有没有什么软件可以辅助

Sketch 在线打开的方法有哪些&#xff1f;这个问题和我之前回答过的「Sketch 可以在线编辑吗&#xff1f;」是一样的答案&#xff0c;没有。很遗憾&#xff0c;Sketch 没有在线打开的方法&#xff0c;Sketch 也做不到可以在线编辑。那么&#xff0c;那些广告里出现的设计软件工…...

CSS Flex 笔记

1. Flexbox 术语 Flex 容器可以是<div> 等&#xff0c;对其设置属性&#xff1a;display: flex, justify-content 是沿主轴方向调整元素&#xff0c;align-items 是沿交叉轴对齐元素。 2. Cheatsheet 2.1 设置 Flex 容器&#xff0c;加粗的属性为默认值 2.1.1 align-it…...

Markdown常用标签及其用途-有示例

Markdown常用标签及其用途 Markdown是一种轻量级标记语言&#xff0c;具有简洁易读的特点。下面是一些常用的Markdown标签以及它们的用途&#xff0c;并附带一些示例&#xff1a; 标题 用于创建不同级别的标题&#xff0c;可通过添加一到六个#符号来表示不同级别的标题。 #…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散

前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说&#xff0c;在叠衣服的过程中&#xff0c;我会带着团队对比各种模型、方法、策略&#xff0c;毕竟针对各个场景始终寻找更优的解决方案&#xff0c;是我个人和我司「七月在线」的职责之一 且个人认为&#xff0c…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...