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 解析: 题意为,给你多个区间(会有重叠),每个区间的每个值都会为这个值累加…...
【业务功能篇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;/*** 操作已经执行成功࿰…...
Fine Logic
登录—专业IT笔试面试备考平台_牛客网 题目大意:有n个数分别为1~n,有m个数值对(u,v)表示u要排在v左边,问至少要多少个排列才能满足所有数值对至少一次 2<n<1e6;1<m<1e6 思路:如果数值对中要求u在v左边,…...
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 协议是超文本传输协议,是客户端浏览器或其他程序“请求”与 Web 服务器响应之间的应用层通信协议。HTTPS主要是由HTTPSSL构建的可进行加密传输、身份认证的一种安全通信通道。32、http 和 https 的区别 ? 1、https协议需要到ca申请证书&…...
Docker 安全及日志管理与https部署
容器的安全性问题的根源在于容器和宿主机共享内核。如果容器里的应用导致Linux内核崩溃,那么整个系统可能都会崩溃。与虚拟机是不同的,虚拟机并没有与主机共享内核,虚拟机崩溃一般不会导致宿主机崩溃。 Docker 容器与虚拟机的区别 虚拟机通…...
2.3 HLSL常用函数
一、函数介绍 函数图像参考网站:Graphtoy 1.基本数学运算 函数 含义 示例图 min(a,b) 返回a、b中较小的数值 mul(a,b) 两数相乘用于矩阵计算 max(a,b) 返回a、b中较大的数值 abs(a) 返回a的绝对值 round(x) 返回与x最近的整数 sqrt(x) 返回x的…...
互联网的发展
概述 互联网是现代社会中举足轻重的一个领域,它的发展对于人类的生活和工作方式产生了深远的影响。互联网的发展经历了几个阶段,从初创阶段到如今的高度普及和深入应用,本文将详细介绍互联网的发展状况。 第一阶段:互联网的起源…...
STM32 CAN通讯实验程序
目录 STM32 CAN通讯实验 CAN硬件原理图 CAN外设原理图 TJA1050T硬件描述 实验线路图 回环实验 CAN头文件配置 CAN_GPIO_Config初始化 CAN初始化结构体 CAN筛选器结构体 接收中断优先级配置 接收中断函数 main文件 实验现象 补充 STM32 CAN通讯实验 CAN硬件原理图…...
Python代码片段之Django静态文件URL的配置
首先要说明这段python代码并不完整,而且我也没有做过测试,只是我在工作时参考了其中的一些个方法。这是我在找python相关源码资料里看到的一段代码,是Django静态文件URL配置代码片段2,代码中有些方法还是挺技巧的,做其…...
基于飞桨paddle的极简方案构建手写数字识别模型测试代码
基于飞桨paddle的极简方案构建手写数字识别模型测试代码 原始测试图片为255X252的图片 因为是极简方案采用的是线性回归模型,所以预测结果数字不一致 本次预测的数字是 [[3]] 测试结果: PS E:\project\python> & D:/Python39/python.exe e:/pro…...
soft ip与hard ip
ip分soft和hard两种,soft就是纯代码,买过来要自己综合自己pr。hard ip如mem和analog与工艺有关。 mem的lib和lef是memory compiler产生的,基于bitcell,是foundry给的。 我正在「拾陆楼」和朋友们讨论有趣的话题,你⼀起…...
MyBatisPlus从入门到精通-2
接着上一讲的Mp的分页功能 下面我们讲解条件查询功能和其他功能 解决一下日志输出和banner问题 每次卞就会输出这些日志 很不美观,现在我们关闭一下 这样建个xml,文件名为logback.xml 文件内容改成这样 配置了logback但是里面什么都没写就不会说有日…...
AI面试官:Asp.Net 中使用Log4Net (一)
AI面试官:Asp.Net 中使用Log4Net (一) 当面试涉及到使用log4net日志记录框架的相关问题时,通常会聚焦在如何在.NET或.NET Core应用程序中集成和使用log4net。以下是一些关于log4net的面试题目,以及相应的解答、案例和代码: 文章目…...
Selenium自动化元素定位方式与浏览器测试脚本
Selenium八大元素定位方法 Selenium可以驱动浏览器完成各种操作,比如模拟点击等。要想操作一个元素,首先应该识别这个元素。人有各种的特征(属性),我们可以通过其特征找到人,如通过身份证号、姓名、家庭住…...
人机交互与人机混合智能的区别
人机交互和人机融合智能是两个相关但不完全相同的概念: 人机交互是指人与计算机之间的信息交流和互动过程。它关注的是如何设计和实现用户友好的界面,以便人们能够方便、高效地与计算机进行沟通和操作。人机交互通常强调用户体验和界面设计,旨…...
【项目】轻量级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 在线打开的方法有哪些?这个问题和我之前回答过的「Sketch 可以在线编辑吗?」是一样的答案,没有。很遗憾,Sketch 没有在线打开的方法,Sketch 也做不到可以在线编辑。那么,那些广告里出现的设计软件工…...
CSS Flex 笔记
1. Flexbox 术语 Flex 容器可以是<div> 等,对其设置属性:display: flex, justify-content 是沿主轴方向调整元素,align-items 是沿交叉轴对齐元素。 2. Cheatsheet 2.1 设置 Flex 容器,加粗的属性为默认值 2.1.1 align-it…...
Markdown常用标签及其用途-有示例
Markdown常用标签及其用途 Markdown是一种轻量级标记语言,具有简洁易读的特点。下面是一些常用的Markdown标签以及它们的用途,并附带一些示例: 标题 用于创建不同级别的标题,可通过添加一到六个#符号来表示不同级别的标题。 #…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
