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

23、区间和

区间和

题目描述

假定有一个无限长的数轴,数轴上每个坐标上的数都是0。

现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。

接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。

输入格式

第一行包含两个整数n和m。

接下来 n 行,每行包含两个整数x和c。

再接下里 m 行,每行包含两个整数l和r。

输出格式

共m行,每行输出一个询问中所求的区间内数字和。

数据范围

$ −109≤x≤109,$
$ 1≤n,m≤10^5,$
$ −109≤l≤r≤109,$
$ −10000≤c≤10000$

输入样例:3 3
1 2
3 6
7 5
1 3
4 6
7 8输出样例:8
0
5

Solution

  1. 用题目中会用到的数字最多有 3 * 10^5,可以用来离散化表示 10^9
  2. alls 存所有用到的下标,adds 存所有添加操作,querys 存所有查询操作
  3. a 存执行添加操作之后的下标的值,q 存前缀和

用二维数组代替 Pairs,用数组代替 List,速度快了一倍

import java.util.*;
import java.io.*;class Main{static final int N = 100010;static int[] a = new int[3 * N];static int[] q = new int[3 * N];static int[][] adds = new int[N][2];static int[][] querys = new int[N][2];static int[] alls = new int[3 * N];public static int unique(int[] alls, int n){// 双指针int j = 0;for(int i = 0; i < n; i++){if(i == 0 || alls[i] != alls[i - 1]){alls[j] = alls[i];j++;}}return j;}public static int bsearch(int[] alls, int n, int x){int low = 0, high = n - 1;while(low <= high){int mid = low + high >> 1;if(alls[mid] > x) high = mid - 1;else if(alls[mid] < x) low = mid + 1;else return mid + 1;}return low;}public static void main(String[] args) throws IOException{BufferedReader br = new BufferedReader(new InputStreamReader(System.in));BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));String[] s = br.readLine().split(" ");int n = Integer.parseInt(s[0]);int m = Integer.parseInt(s[1]);// 下标int idx = 0, idx1 = 0;// 存插入for(int i = 0; i < n; i++){s = br.readLine().split(" ");int x = Integer.parseInt(s[0]);int c = Integer.parseInt(s[1]);alls[idx++] = x;adds[i][0] = x;adds[i][1] = c;}for(int i = 0; i < m; i++){s = br.readLine().split(" ");int l = Integer.parseInt(s[0]);int r = Integer.parseInt(s[1]);alls[idx++] = l;alls[idx++] = r;querys[i][0] = l;querys[i][1] = r;}// alls(0, idx - 1) 排序Arrays.sort(alls, 0, idx);// 去重int end = unique(alls, idx);// 添加操作for(int i = 0; i < n; i++){// 二分查找找到 x 在 alls 数组中的下标int t = bsearch(alls, end, adds[i][0]);a[t] += adds[i][1];}// 计算前缀和for(int i = 1; i <= end; i++){q[i] = q[i - 1] + a[i];}for(int i = 0; i < m; i++){int l = bsearch(alls, end, querys[i][0]);int r = bsearch(alls, end, querys[i][1]);bw.write(q[r] - q[l - 1] + "\n");}bw.close();br.close();}
}

用了 List 和 Pairs,效率不高

import java.util.*;
import java.io.*;public class Main{static class Pairs{int first, second;public Pairs(int first, int second){this.first = first;this.second = second;}}public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));String[] s = in.readLine().split(" ");int n = Integer.parseInt(s[0]);int m = Integer.parseInt(s[1]);// 数据范围为 10 的 9 次方,如果直接一个数组来存,空间就会超出限制// 但是操作数和查询数只有 10 的 5 次方// 想到用离散化的方式,用 10 的 5 次方的长度表示 10 的 9 次方的量级// 申请的数组长度 n + m + m + 10 就可以,加个 10 防止边界问题int N = n + m + m + 10;// a[] 去重,离散化之后的数组int[] a = new int[N];// p[] a的前缀和int[] p = new int[N];// adds 记录添加操作List<Pairs> adds = new ArrayList<>();// querys 记录查询操作List<Pairs> querys = new ArrayList<>();// alls 记录所有在数轴上出现过的坐标List<Integer> alls = new ArrayList<>();for(int i = 0; i < n; i++){s = in.readLine().split(" ");int x = Integer.parseInt(s[0]);int c = Integer.parseInt(s[1]);adds.add(new Pairs(x, c));alls.add(x);}for(int i = 0; i < m; i++){s = in.readLine().split(" ");int l = Integer.parseInt(s[0]);int r = Integer.parseInt(s[1]);querys.add(new Pairs(l, r));alls.add(l);alls.add(r);}// 排序Collections.sort(alls);// 去重int end = unique(alls);alls = alls.subList(0, end);// 离散化,就是找到要插入或者查询的数字在 alls 的位置// 可以用二分查找// 插入// 返回值以 1 开始计数for(int i = 0; i < n; i++){int index = bsearch(adds.get(i).first, alls);a[index] += adds.get(i).second;}// 计算前缀和for(int i = 1; i < N; i++){p[i] = p[i - 1] + a[i];}// 开始查询输出for(int i = 0; i < m; i++){int l = bsearch(querys.get(i).first, alls);int r = bsearch(querys.get(i).second, alls);int res = p[r] - p[l - 1];out.write(res + "\n");out.flush();}}public static int unique(List<Integer> list){int j = 0;for(int i = 0; i < list.size(); i++){if(i == 0 || list.get(i) != list.get(i - 1)){list.set(j, list.get(i));j++;}}return j;}public static int bsearch(int x, List<Integer> list){int l = 0, r = list.size() - 1;while(l <= r){int mid = l + r >> 1;if(list.get(mid) > x) r = mid - 1;else if(list.get(mid) < x) l = mid + 1;else return mid + 1;}return 1;}
}

yxc

  1. 离散化

在这里插入图片描述

相关文章:

23、区间和

区间和 题目描述 假定有一个无限长的数轴&#xff0c;数轴上每个坐标上的数都是0。 现在&#xff0c;我们首先进行 n 次操作&#xff0c;每次操作将某一位置x上的数加c。 接下来&#xff0c;进行 m 次询问&#xff0c;每个询问包含两个整数l和r&#xff0c;你需要求出在区间…...

Python零基础从小白打怪升级中~~~~~~~文件和文件夹的操作 (1)

第七节&#xff1a;文件和文件夹的操作 一、IO流&#xff08;Stream&#xff09; 通过“流”的形式允许计算机程序使用相同的方式来访问不同的输入/输出源。stream是从起源&#xff08;source&#xff09;到接收的&#xff08;sink&#xff09;的有序数据。我们这里把输入/输…...

Qt plugin 开发UI界面插件

目录 1.创建接口 2.创建插件 3.创建插件界面 4.插件实现 5.创建应用工程 6.应用插件 1.创建接口 打开QtCreater&#xff0c;点击左上角“文件”->新建文件或项目&#xff0c;在弹窗中选择C/CHeader File。 输入文件名&#xff0c;选好路径&#xff08;可自行设置名称…...

Android查看SO库的依赖

➜ bin pwd /Users/xxx/Library/Android/sdk/ndk/21.1.6352462/toolchains/aarch64-linux-android-4.9/prebuilt/darwin-x86_64/bin ➜ bin ./aarch64-linux-android-readelf -d /Download/libxxx.so 0x0000000000000001 (NEEDED) Shared library: [liblog.so]0x…...

麒麟KOS删除鼠标右键新建菜单里不需要的选项

原文链接&#xff1a;麒麟KOS删除鼠标右键新建菜单里不需要的选项 Hello&#xff0c;大家好啊&#xff01;在日常使用麒麟KOS操作系统时&#xff0c;我们可能会发现鼠标右键新建菜单里包含了一些不常用或者不需要的选项。这不仅影响我们的使用效率&#xff0c;也让菜单显得杂乱…...

DPDK系列之四十二DPDK应用网络编程UDP编程

一、UDP编程 UDP编程的应用和TCP编程的应用同样非常广泛&#xff0c;如果说真得想使用UDP编程&#xff0c;一般情况下还真得不至于运用DPDK这种重量级的框架。但一个框架的优秀与否&#xff0c;不仅仅在于自身的整体设计优秀&#xff0c;更重要的在于其对应用的支持更完善。 正…...

金三银四面试题(十九):MySQL中的锁

在MySQL中&#xff0c;锁是非常重要的&#xff0c;特别是在多用户并发访问数据库的环境中&#xff0c;因此也是面试中常问的话题。 请说说数据库的锁&#xff1f; 关于MySQL 的锁机制&#xff0c;可能会问很多问题&#xff0c;不过这也得看面试官在这方面的知识储备。 MySQL …...

【JavaScript】原型链/作用域/this指针/闭包

1.原型链 参考资料&#xff1a;Annotated ES5 ECMAScript起初并不支持如C、Smalltalk 或 Java 中“类”的形式创建对象&#xff0c;而是通过字面量表示法或者构造函数创建对象。每个构造函数都是一个具有名为“prototype”的属性的函数&#xff0c;该属性用于实现基于原型的继…...

Python的MATLAB使用

Python和MATLAB是两种不同的编程语言&#xff0c;它们各自拥有不同的生态系统和库。然而&#xff0c;你可以在Python中使用一些方法来实现与MATLAB类似的功能。以下是一些方法和库&#xff0c;可以帮助你在Python中实现MATLAB风格的编程&#xff1a; 1. NumPy: NumPy是Python中…...

文件输入/输出流(I/O)

文章目录 前言一、文件输入\输出流是什么&#xff1f;二、使用方法 1.FileInputStream与FileOutputStream类2.FileReader与FileWriter类总结 前言 对于文章I/O(输入/输出流的概述)&#xff0c;有了下文。这篇文章将具体详细展述如何向磁盘文件中输入数据&#xff0c;或者读取磁…...

docker,schedule job和environment variables三者的含义与区别

这三个概念在软件开发和部署中扮演着不同的角色&#xff1a; Docker一般长这样&#xff1a;superlifestyle/sscp-api Schedule Job一般长这样&#xff1a;recorrect_ocr_receipt_status 、Sync2D365 Environment Variables一般长这样&#xff1a;D365_BATCH_OPERATION_SIZE ima…...

90天玩转Python—16—基础知识篇:面向对象知识详解

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇:C站最全Python标准库总结 90天玩转Python--02--基础知识篇:初识Python与PyCharm 90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装) 90天玩转Python—04—基础知识篇:Pytho…...

python 标准库之openpyxl的常规操作

目录 openpyxl&#xff08;Excel文件处理模块&#xff09; 读sheet 读sheet中单元格 合并单元格 openpyxl模块基本用法 安装方法 基本使用 读取Excel文档 &#xff08;一&#xff09;获取工作表 &#xff08;二&#xff09;获取单元格 &#xff08;三&#xff09;获取…...

90天玩转Python—12—基础知识篇:Python自动化操作Email:发送邮件、收邮件与邮箱客户端操作全解析

90天玩转Python系列文章目录 90天玩转Python—01—基础知识篇:C站最全Python标准库总结 90天玩转Python--02--基础知识篇:初识Python与PyCharm 90天玩转Python—03—基础知识篇:Python和PyCharm(语言特点、学习方法、工具安装) 90天玩转Python—04—基础知识篇:Pytho…...

利用lidar_align来进行lidar和imu标定

文章目录 下载并安装lidar_align安装nlopt迁移NLOPTConfig.cmake修改loader.cpp文件编译并运行 下载并安装lidar_align mkdir -p lidar_align/src cd lidar_align/src git clone https://github.com/ethz-asl/lidar_align.git安装nlopt git clone http://github.com/steven…...

牛客NC93 设计LRU缓存结构【hard 链表,Map Java】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84 思路 双向链表map最新的数据放头结点&#xff0c;尾节点放最老的数据&#xff0c;没次移除尾巴节点本地考察链表的新增&#xff0c;删除&#xff0c;移动节点参考答案Java im…...

机器学习和深度学习 -- 李宏毅(笔记与个人理解1-6)

机器学习和深度学习教程 – 李宏毅&#xff08;笔记与个人理解&#xff09; day1 课程内容 什么是机器学习 找函数关键技术&#xff08;深度学习&#xff09; 函数 – 类神经网络来表示 &#xff1b;输入输出可以是 向量或者矩阵等如何找到函数&#xff1a; supervised Lear…...

低功耗全极霍尔开关芯片 D02,磁性开关点精确,对工艺和温度变化不敏感

1、概述 D02 是一款低功耗全极霍尔开关&#xff0c;用于检测施加的磁通量密度&#xff0c;并提供一个数字输出&#xff0c;该输出指示所感测磁通量幅度的当前状态。这些应用的一个例子是翻盖手机中的 ON/OFF 开关。微功耗设计特别适合电池供电系统&#xff0c;如手机或笔记本电…...

初识--数据结构

什么是数据结构&#xff1f;我们为什么要学习数据结构呢....一系列的问题就促使我们不得不了解数据结构。我们不禁要问了&#xff0c;学习C语言不就够了吗&#xff1f;为什么还要学习数据结构呢&#xff1f;这是因为&#xff1a;数据结构能够解决C语言解决不了的问题&#xff0…...

人工智能前沿成科技竞争新高地

以下文章来源&#xff1a;经济参考报 近日&#xff0c;首届中国具身智能大会&#xff08;CEAI 2024&#xff09;在上海举行。作为人工智能领域的前沿热点&#xff0c;具身智能正逐步走进现实&#xff0c;成为当前全球科技竞争的新高地、未来产业的新赛道、经济发展的新引擎。 “…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...