离散化算法总结
离散化是将大范围的数字映射到小范围的区间内,适用于稀疏的区间。
两个问题需要考虑:
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 映射的注解,可用于类或…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...
DiscuzX3.5发帖json api
参考文章:PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下,适配我自己的需求 有一个站点存在多个采集站,我想通过主站拿标题,采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...
书籍“之“字形打印矩阵(8)0609
题目 给定一个矩阵matrix,按照"之"字形的方式打印这个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为:1,…...
TJCTF 2025
还以为是天津的。这个比较容易,虽然绕了点弯,可还是把CP AK了,不过我会的别人也会,还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...
boost::filesystem::path文件路径使用详解和示例
boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类,封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解,包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...
