离散化算法总结
离散化是将大范围的数字映射到小范围的区间内,适用于稀疏的区间。
两个问题需要考虑:
1. 原数组中可能有重复元素,需要去重。
2. 如何算出离散化后的值(离散化后保序,使用二分)。
题目链接:
https://www.acwing.com/problem/content/804/
代码:
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;typedef pair<int, int> PII;const int N = 300010;int n, m;
int a[N], s[N];vector<int> alls;
vector<PII> add, query;int find(int x)
{int l = 0, r = alls.size() - 1;while (l < r){int mid = l + r >> 1;if (alls[mid] >= x) r = mid;else l = mid + 1;}return r + 1;
}int main()
{cin >> n >> m;for (int i = 0; i < n; i++){int x, c;cin >> x >> c;add.push_back({x, c});alls.push_back(x);}for (int i = 0; i < m; i++){int l, r;cin >> l >> r;query.push_back({l, r});alls.push_back(l);alls.push_back(r);}// 去重sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());// 处理插入for (auto item : add){int x = find(item.first);a[x] += item.second;}// 预处理前缀和for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];// 处理询问for (auto item : query){int l = find(item.first), r = find(item.second);cout << s[r] - s[l - 1] << endl;}return 0;
}
其中,unique(alls.begin(), alls.end())将数组中的所有重复元素去重,返回去重后的数组的尾端点。使用Java和Python的小伙伴可以使用下列自己实现的方法替换(双指针算法):
vector<int>::iterator unique(vector<int>& a)
{int j = 0;for (int i = 0; i < a.size(); i++)if (!i || a[i] != a[i - 1])a[j++] = a[i];// a[0] ~ a[j - 1] 所有a中不重复的数return a.begin() + j;
}
相关文章:
离散化算法总结
离散化是将大范围的数字映射到小范围的区间内,适用于稀疏的区间。 两个问题需要考虑: 1. 原数组中可能有重复元素,需要去重。 2. 如何算出离散化后的值(离散化后保序,使用二分)。 题目链接: …...
【海思SS528 | VO】MPP媒体处理软件V5.0 | VO模块编程总结
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 🤣本文内容🤣&a…...
逻辑卷管理器lvm
啥意思,个人理解就是可以将物理分区合并一起组成大的磁盘,也可以移除其中的某个分区。 有四个概念需要了解下 PV,物理卷,VG 卷用户组,PE物理扩展块,LV逻辑卷 p物理,v卷,g用户组&a…...
函数声明后的“ - >”是什么?
这种语法的优势之一是可以在函数的返回类型中使用函数参数,使得返回类型更灵活。 先来看一个使用尾返回类型的例子: #include <iostream> auto add(int a, int b) -> int {return a b; }int main() {std::cout << add(3, 4) <<…...
51爱心流水灯32灯炫酷代码
源代码摘自远眺883的文章,大佬是30个灯的,感兴趣的铁汁们可以去看看哦~(已取得原作者的许可):基于STC89C51单片机设计的心形流水灯软件代码部分_单片机流水灯代码_远眺883的博客-CSDN博客 由于博主是个小菜鸡ÿ…...
将不同时间点的登录状态记录转化为不同时间段的相同登录状态SQL求解
题目 有不同时间点的登录状态记录表state_log如下 请使用sql将其转化为如下表的不同时间段的相同登录状态记录 思路分析: 此类问题需要用到lag或lead函数取上下行对应的数据,然后对前后结果做比较打标签(0或1),再…...
正则表达式与SQL数据库教程
使用正则表达式通过用例查询 Postgres 数据库: 正则表达式(又名 Regex) 正则表达式是一个强大的工具,广泛用于模式匹配和文本操作。 几乎所有编程语言都支持它们,并且经常用于文本提取、搜索和匹配文本等用例。 正则…...
HTML_web扩展标签
1.表格标签 2.增强表头表现 4.表格属性(实际不常用) 结构标签: 合并单元格: 更多请查看主页...
论文阅读:Distributed Initialization for VVIRO with Position-Unknown UWB Network
前言 Distributed Initialization for Visual-Inertial-Ranging Odometry with Position-Unknown UWB Network这篇论文是发表在ICRA 2023上的一篇文章,本文提出了一种基于位置未知UWB网络的一致性视觉惯性紧耦合优化测距算法( DC-VIRO )的分布式初始化方法。 对于…...
scrapy爬虫中间件和下载中间件的使用
一、关于中间件 之前文章说过,scrapy有两种中间件:爬虫中间件和下载中间件,他们的作用时间和位置都不一样,具体区别如下: 爬虫中间件(Spider Middleware) 作用: 爬虫中间件主要负…...
手敲单链表,简单了解其运行逻辑
1. 链表 1.1 结构组成 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。 链表的结构如下图所示,是由很多个节点相互通过引用来连接而成的;每一个节点由两部分组成,分别数据域&…...
Redis RDB
基于内存的 Redis, 数据都是存储在内存中的。 那么如果重启的话, 数据就会丢失。 为了解决这个问题, Redis 提供了 2 种数据持久化的方案: RDB 和 AOF。 RDB 是 Redis 默认的持久化方案。当满足一定条件的时候, 会把当前内存中的数据写入磁盘, 生成一个快照文件 dump.rdb。Redi…...
Elasticsearch一些函数查询
1. 根据价格分组统计数量,每组区间为2000, filter_pathaggregations 设置查询结果只展示函数结果 也有date_histogram函数根据日期分组等等 GET order/_search?filter_pathaggregations {"aggs": {"hist_price": {"histogr…...
竞赛选题 : 题目:基于深度学习的水果识别 设计 开题 技术
1 前言 Hi,大家好,这里是丹成学长,今天做一个 基于深度学习的水果识别demo 这是一个较为新颖的竞赛课题方向,学长非常推荐! 🧿 更多资料, 项目分享: https://gitee.com/dancheng-senior/pos…...
Linux expect命令详解
在Linux系统中,expect 是一款非常有用的工具,它允许用户自动化与需要用户输入进行交互的程序。本文将深入探讨expect命令的基本语法、使用方法以及一些最佳实践。 什么是Expect命令? expect 是一个用于自动化交互式进程的工具。它的主要功能…...
ubuntu18编译Android8的Failed to contact Jack server问题
环境 ubuntu18.04 Android8.1.0 步骤 安装环境 apt install git-core apt install gnupg apt install flex apt install bison apt install gperf apt install build-essential apt install curl apt install libc6-dev apt install libssl-dev apt install libncurses5-dev:…...
FindSecBugs支持的检测规则
很多SAST集成了FindSecBugs这个开源工具,其好处是直接对Class文件进行检测,也就是直接检测二进制问题,可以直接检测war、jar,还是非常方便的。虽然误报率较高,但是这些检测出来的安全漏洞很多是安全从业人员耳熟能详的…...
【WPF.NET开发】WPF.NET桌面应用开发概述
本文内容 为何从 .NET Framework 升级使用 WPF 进行编程标记和代码隐藏输入和命令控件布局数据绑定图形和动画文本和版式自定义 WPF 应用 Windows Presentation Foundation (WPF) 是一个与分辨率无关的 UI 框架,使用基于矢量的呈现引擎,构建用于利用现…...
态势感知是什么
在当今高度信息化的时代,信息安全风险已经成为企业、政府和个人的重要关注点。为了有效应对这些风险,态势感知成为了一种日益重要的能力。态势感知是一种基于环境的、动态、整体地洞悉安全风险的能力,是以安全大数据为基础,从全局…...
Spring MVC常用的注解, Controller注解的作用,RequestMapping注解的作用 @ResponseBody注解的作用
文章目录 Spring MVC常用的注解和注解的相关作用Controller注解的作用RequestMapping注解的作用ResponseBody注解的作用PathVariable和RequestParam的区别 Spring MVC常用的注解和注解的相关作用 RequestMapping:用于处理请求 url 映射的注解,可用于类或…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join
纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...
