AcWing 802. 区间和 离散化

文章目录

  • 题目链接
  • 题目描述
  • 解题思路
  • 代码实现
  • 总结


题目链接

链接: AcWing 802. 区间和

题目描述

在这里插入图片描述

解题思路

离散化是一种常用的技巧,它能够将原始的连续数值转换为一组离散的值,从而简化问题的处理。在这段代码中,离散化的过程主要分为三个步骤。

第一步是将需要进行离散化的数值(在这里是add数组和query数组中的x、l、r值)存储到一个数组中(这里是alls数组)。这一步是为了之后的去重和排序做准备。

第二步是对存储了所有待离散化数值的数组进行去重和排序操作。通过这一步,我们得到了一个不重复且有序的离散化数组,能够完整地覆盖所有需要处理的数值。

第三步是使用离散化后的数值进行替换和处理。在这段代码中,对add数组中的操作和query数组中的查询都是通过离散化后的位置来进行处理的,而不再直接使用原始的连续数值。这样做的好处是,在处理过程中不再受到原始数值的大小和分布的影响,简化了问题的处理过程。

离散化核心代码

 //离散化
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

代码实现

#include<iostream>
#include <vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=3e6+10;
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;//因为使用前缀和,其下标要+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;
}

总结

存储数值:将需要离散化的数值存储到一个数组中,如add和query数组中的x、l、r值都存储在alls数组中。

去重和排序:对存储了所有待离散化数值的数组进行去重和排序操作,得到一个不重复且有序的离散化数组。

替换和处理:使用离散化后的数值进行替换和处理。在这段代码中,操作和查询都是通过离散化后的位置来进行处理的,简化了问题的处理过程。

离散化的目的是将连续的数值转换为离散的数值,从而简化问题的处理。通过离散化,可以减少对原始数值大小和分布的敏感性,使问题的处理更加简单和高效。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/384857.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

探索Nginx:强大的开源Web服务器与反向代理

一、引言 随着互联网的飞速发展&#xff0c;Web服务器在现代技术架构中扮演着至关重要的角色。Nginx&#xff08;发音为“engine x”&#xff09;是一个高性能的HTTP和反向代理服务器&#xff0c;也是一个IMAP/POP3/SMTP代理服务器。Nginx因其卓越的性能、稳定性和灵活性&…

02.数据结构

一、链表 作用&#xff1a;用于写邻接表&#xff1b; 邻接表作用&#xff1a;用于存储图或树&#xff1b; 1、用数组模拟单链表 #include<iostream> using namespace std;const int N 100010;// head 表示头结点的下标 // e[i] 表示结点i的值 // ne[i] 表示结点i的ne…

前端工程化面试题 | 08.精选前端工程化高频面试题

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

DS Wannabe之5-AM Project: DS 30day int prep day14

Q1. What is Autoencoder? 自编码器是什么&#xff1f; 自编码器是一种特殊类型的神经网络&#xff0c;它通过无监督学习尝试复现其输入数据。它通常包含两部分&#xff1a;编码器和解码器。编码器压缩输入数据成为一个低维度的中间表示&#xff0c;解码器则从这个中间表示重…

CentOS 7.9安装Tesla M4驱动、CUDA和cuDNN

正文共&#xff1a;1333 字 21 图&#xff0c;预估阅读时间&#xff1a;2 分钟 上次我们在Windows上尝试用Tesla M4配置深度学习环境&#xff08;TensorFlow识别GPU难道就这么难吗&#xff1f;还是我的GPU有问题&#xff1f;&#xff09;&#xff0c;但是失败了。考虑到Windows…

BIO、NIO、Netty演化总结

关于BIO&#xff08;关于Java NIO的的思考-CSDN博客&#xff09;和NIO&#xff08;关于Java NIO的的思考-CSDN博客&#xff09;在之前的博客里面已经有详细的讲解&#xff0c;这里再总结一下最近学习netty源码的的心得体会 在之前的NIO博客中我们知道接受客户端连接和IO事件的…

Vulnhub靶机:hacksudo-ProximaCentauri

一、介绍 运行环境&#xff1a;Virtualbox 攻击机&#xff1a;kali&#xff08;10.0.2.15&#xff09; 靶机&#xff1a;hacksudo-ProximaCentauri&#xff08;10.0.2.51&#xff09; 目标&#xff1a;获取靶机root权限和flag 靶机下载地址&#xff1a;https://www.vulnhu…

算法学习——LeetCode力扣二叉树篇4

算法学习——LeetCode力扣二叉树篇4 222. 完全二叉树的节点个数 222. 完全二叉树的节点个数 - 力扣&#xff08;LeetCode&#xff09; 描述 给你一棵 完全二叉树 的根节点 root &#xff0c;求出该树的节点个数。 完全二叉树 的定义如下&#xff1a;在完全二叉树中&#xf…

二叉树、堆和堆排序(优先队列)

前言&#xff1a; 本章会讲解二叉树及其一些相关练习题&#xff0c;和堆是什么。 二叉树&#xff1a; 二叉树的一些概念&#xff1a; 一棵二叉树是有限节点的集合&#xff0c;该集合可能为空。二叉树的特点是每一个节点最多有两个子树&#xff0c;即二叉树不存在度大于2的节点…

中科大计网学习记录笔记(十):P2P 应用

前言&#xff1a; 学习视频&#xff1a;中科大郑烇、杨坚全套《计算机网络&#xff08;自顶向下方法 第7版&#xff0c;James F.Kurose&#xff0c;Keith W.Ross&#xff09;》课程 该视频是B站非常著名的计网学习视频&#xff0c;但相信很多朋友和我一样在听完前面的部分发现信…

全坚固平板EM-I12U,全新升级后的优质体验

平板终端机在户外勘探、制造业、畜牧业、银行金融行业当中都不是陌生的&#xff0c;能采集各种数据来转换成信息流向企业和行业的各个分支当中&#xff0c;在整个行业发展、社会推动上面都起着关键性作用&#xff0c;而平板终端机的升级也就意味着未来的这些行业发展会进入一个…

【51单片机】LED点阵屏(江科大)

9.1LED点阵屏 1.LED点阵屏介绍 LED点阵屏由若干个独立的LED组成,LED以矩阵的形式排列,以灯珠亮灭来显示文字、图片、视频等。 2.LED点阵屏工作原理 LED点阵屏的结构类似于数码管,只不过是数码管把每一列的像素以“8”字型排列而已。原理图如下 每一行的阳极连在一起,每一列…

C++ //练习 6.3 编写你自己的fact函数,上机检查是否正确。

C Primer&#xff08;第5版&#xff09; 练习 6.3 练习 6.3 编写你自己的fact函数&#xff0c;上机检查是否正确。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 代码块 /********************************************************…

VMware虚拟机安装openEuler系统(二)(2024)

下面我们进行openEuler系统的一些简单配置。 1. 开启openEuler系统 在VMware Workstation Pro虚拟机软件中找到安装好的openEuler操作系统虚拟机并开启。 等待开启。 2. 安装配置 进入后选择第一个“Install openEuler 20.03-LTS”。 3. 选择系统语言 为虚拟机设置系统语言…

Unity学习笔记(零基础到就业)|Chapter02:C#基础

Unity学习笔记&#xff08;零基础到就业&#xff09;&#xff5c;Chapter02:C#基础 前言一、复杂数据&#xff08;变量&#xff09;类型part01&#xff1a;枚举数组1.特点2.枚举&#xff08;1&#xff09;基本概念&#xff08;2&#xff09;申明枚举变量&#xff08;3&#xff…

C++多态重难点

CSDN上已经有很多关于C多态方面的一些系统介绍了&#xff0c;但是我看了一下一些有关于多态问题的细节问题文章较少&#xff0c;因此我想要出一片文章重点讲一讲我认为比较重点且容易被遗忘的知识点&#xff0c;一些比较基本的知识这里就不过多赘述了&#xff0c;可以参考其他优…

LabVIEW智能温度监控系统

LabVIEW智能温度监控系统 介绍了一个基于LabVIEW的智能温度监控系统&#xff0c;实现对工业环境中温度的实时监控与调控。通过集成传感器技术和LabVIEW软件平台&#xff0c;系统能够自动检测环境温度&#xff0c;及时响应温度变化&#xff0c;并通过图形用户界面(GUI)为用户提…

【51单片机】AT24C02(江科大、爱上半导体)

一、AT24C02 1.AT24C02介绍 AT24C02是一种可以实现掉电不丢失的存储器,可用于保存单片机运行时想要永久保存的数据信息 存储介质:E2PROM 通讯接口:12C总线 容量:256字节 2.引脚即应用电路 本开发板AT24C02原理图 12C地址全接地,即全为0 WE接地,没有写使能 SCL接P21 S…

Obsidian Publish的开源替代品Perlite

前几天就有网友跟我说&#xff0c;freenom 的免费域名不可用了&#xff0c;10 号的时候老苏进后台看了一下&#xff0c;还有一半的域名显示为 ACTIVE&#xff0c;似乎是以 2024年6月 为限。但到 11 号&#xff0c;老苏发现博客 (https://laosu.cf) 已经访问不了了&#xff0c;这…

使用SpringMVC实现功能

目录 一、计算器 1、前端页面 2、服务器处理请求 3、效果 二、用户登陆系统 1、前端页面 &#xff08;1&#xff09;登陆页面 &#xff08;2&#xff09;欢迎页面 2、前端页面发送请求--服务器处理请求 3、效果 三、留言板 1、前端页面 2、前端页面发送请求 &…