【基础】离散化

2024-09-01 00:52
文章标签 基础 离散

本文主要是介绍【基础】离散化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 模板

vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end());   // 去掉重复元素// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
}

 

AcWing 802. 区间和 - AcWing

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

现在,我们首先进行 nn 次操作,每次操作将某一位置 xx 上的数加 cc。

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

输入格式

第一行包含两个整数 nn 和 mm。

接下来 nn 行,每行包含两个整数 xx 和 cc。

再接下来 mm 行,每行包含两个整数 ll 和 rr。

输出格式

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

数据范围

−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000

输入样例:

Copy

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

Copy

8
0
5
难度:简单
时/空限制:2s / 64MB
总通过数:98846
总尝试数:172775
来源:

模板题

算法标签

挑战模式

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#define pii pair<int,int>
int n,m;
vector<int> alls;
vector<pii> add;
vector<pii> query;
const int N=300010;
int a[N],s[N];//总体而言,是把操作存进去,统计了要看哪一些,载重新取出来int findd(int x){int l=0,r=alls.size()-1;//l,r是可以取到的while(l<r){int mid=(l+r)>>1;if(alls[mid]>=x)r=mid;else l=mid+1;}return r+1;//新的从1存
}int main(){cin>>n>>m;for(int i=1;i<=n;i++){int x,c;cin>>x>>c;add.push_back({x,c});alls.push_back(x);}for(int i=1;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=findd(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=findd(item.first);int r=findd(item.second);cout<<s[r]-s[l-1]<<endl;}}

这篇关于【基础】离散化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1125486

相关文章

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

安装centos8设置基础软件仓库时出错的解决方案

《安装centos8设置基础软件仓库时出错的解决方案》:本文主要介绍安装centos8设置基础软件仓库时出错的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录安装Centos8设置基础软件仓库时出错版本 8版本 8.2.200android4版本 javas

Linux基础命令@grep、wc、管道符的使用详解

《Linux基础命令@grep、wc、管道符的使用详解》:本文主要介绍Linux基础命令@grep、wc、管道符的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录grep概念语法作用演示一演示二演示三,带选项 -nwc概念语法作用wc,不带选项-c,统计字节数-

python操作redis基础

《python操作redis基础》Redis(RemoteDictionaryServer)是一个开源的、基于内存的键值对(Key-Value)存储系统,它通常用作数据库、缓存和消息代理,这篇文章... 目录1. Redis 简介2. 前提条件3. 安装 python Redis 客户端库4. 连接到 Re

SpringBoot基础框架详解

《SpringBoot基础框架详解》SpringBoot开发目的是为了简化Spring应用的创建、运行、调试和部署等,使用SpringBoot可以不用或者只需要很少的Spring配置就可以让企业项目快... 目录SpringBoot基础 – 框架介绍1.SpringBoot介绍1.1 概述1.2 核心功能2

Spring Boot集成SLF4j从基础到高级实践(最新推荐)

《SpringBoot集成SLF4j从基础到高级实践(最新推荐)》SLF4j(SimpleLoggingFacadeforJava)是一个日志门面(Facade),不是具体的日志实现,这篇文章主要介... 目录一、日志框架概述与SLF4j简介1.1 为什么需要日志框架1.2 主流日志框架对比1.3 SLF4

Spring Boot集成Logback终极指南之从基础到高级配置实战指南

《SpringBoot集成Logback终极指南之从基础到高级配置实战指南》Logback是一个可靠、通用且快速的Java日志框架,作为Log4j的继承者,由Log4j创始人设计,:本文主要介绍... 目录一、Logback简介与Spring Boot集成基础1.1 Logback是什么?1.2 Sprin

MySQL复合查询从基础到多表关联与高级技巧全解析

《MySQL复合查询从基础到多表关联与高级技巧全解析》本文主要讲解了在MySQL中的复合查询,下面是关于本文章所需要数据的建表语句,感兴趣的朋友跟随小编一起看看吧... 目录前言:1.基本查询回顾:1.1.查询工资高于500或岗位为MANAGER的雇员,同时还要满足他们的姓名首字母为大写的J1.2.按照部门

Android Mainline基础简介

《AndroidMainline基础简介》AndroidMainline是通过模块化更新Android核心组件的框架,可能提高安全性,本文给大家介绍AndroidMainline基础简介,感兴趣的朋... 目录关键要点什么是 android Mainline?Android Mainline 的工作原理关键

mysql的基础语句和外键查询及其语句详解(推荐)

《mysql的基础语句和外键查询及其语句详解(推荐)》:本文主要介绍mysql的基础语句和外键查询及其语句详解(推荐),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋... 目录一、mysql 基础语句1. 数据库操作 创建数据库2. 表操作 创建表3. CRUD 操作二、外键