首页 > 其他分享 >区间和---使用离散化

区间和---使用离散化

时间:2024-10-31 19:30:57浏览次数:4  
标签:离散 int back mid --- item alls push 区间

假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行n次操作,每次操作将某一位置 x 上的数加 c 。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r]之间的所有数的和。

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector< int > alls;
vector <pair<int , int>> add, query;

int a[300010] , b[300010];

int find(int x){
    
    int l = 0 , r = alls.size() - 1;
    
    while(l < r){
        int mid = (l + r) >> 1;
        
        if(x > alls[mid]) l = mid + 1;
        else r = mid;
    }
    
    return r + 1;
}

int main(){
    int n , m ;
    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 < 300010 ; i ++) b[i] = a[i] + b[i - 1];
    
    for(auto item : query){
        int l = find(item.first);
        int r = find(item.second);
        
        cout << b[r] - b[l - 1] << endl;
        
    }
    
    return 0;
}

标签:离散,int,back,mid,---,item,alls,push,区间
From: https://www.cnblogs.com/lxy54/p/18518726

相关文章

  • 《程序员修炼之道:从小工到专家》阅读笔记2---软件熵的理解与警惕
    《程序员修炼之道:从小工到专家》中提出的“软件熵”概念,犹如一记警钟,在我的脑海中久久回荡。软件熵,即系统中“无序”的总量。随着时间的推移,如果不及时处理低劣的设计、糟糕的代码和低质的文档等问题,软件就会像一个无人打理的房间一样,逐渐变得混乱不堪。这种无序状态不仅会影......
  • Navicat 连接 MySQL 失败:2002-can‘t connect to server on localhost(10061)问题解决
    连接不上问题可能有如下原因服务器安全组中没有配置3306端口mysql服务端口只开放本地了如下:修改/etc/mysql/mysql.conf.d/mysqld.cnf中bind-address和mysqlx-bind-address注释掉重启mysql服务systemctlrestartmysqlmysql登录用户的host为localhost只允......
  • # 20222316 2024-2025-1 《网络与系统攻防技术》实验三实验报告
    一、实验内容1.学习总结1)免杀基本概念英文为Anti-AntiVirus(简写VirusAV),逐字翻译为“反-反病毒”,翻译为“反杀毒技术”。一般是对恶意软件做处理,让它不被杀毒软件所检测。也是渗透测试中需要使用到的技术。2)免杀技术修改特征码修改校验和花指令免杀花指令其实......
  • Yaml中特殊符号"| > |+ |-"的作用
    "|",保留每行尾部的换行符\n。">",删除每行尾部的换行符\n,则看似多行文本,则在程序中会将其视为一行。include_newlines:|exactlyasyouseewillappearthesethreelinesofpoetryfold_newlines:>thisisreallya......
  • 【PTA 编程题 7-3 】矩形运算 #C语言
    代码#include<stdio.h>#defineMAXM10#defineMAXN10intmain(void){intn;scanf("%d",&n);inta[MAXM][MAXN];for(inti=0;i<n;i++){for(intj=0;j<n;j++){scanf("%d",&a[i][j]);......
  • DVD管理系统 (连接数据库--项目模拟)
    本章主要是增加和查看功能,其他的删除和修改(借出/归还)只是写了工具类和接口DVD类属性----必须与数据库里面,我们所调用的表一一对应!!!!packagedvd.entry;/***实体类---一对一参照表*表名=类名(首字母大写)*字段名===属性名*字段类型==属性类型*/publicclas......
  • NOIP 模拟赛:2024-10-30
    T1:一场比赛一共有\(n\)位选手和\(m\)道题目,其中你是第\(1\)位选手。你现在知道了每位选手通过了哪些题目。你可以调整题目的顺序,然后给题目赋予一个分值,使得第\(i\)道题目的分值是\(2^i\)。你想知道能否通过调整题目的顺序,使得你的成绩恰好是第二高的。保证不存在两个选手的通......
  • 学习高校课程-软件设计模式-享元模式和代理模式(lec8)
    原文链接Flyweight:ProblemEachparticle,suchasabullet,amissileorapieceofshrapnelwasrepresentedbyaseparateobjectcontainingplentyofdata.Atsomepoint,whenthecarnageonaplayer’sscreenreacheditsclimax,newlycreatedparticlesno......
  • Goby 漏洞发布|Apache Solr /solr/admin/info/properties:/admin/info/key 权限绕过漏
    漏洞名称:ApacheSolr/solr/admin/info/properties:/admin/info/key权限绕过漏洞(CVE-2024-45216)EnglishName:ApacheSolr/solr/admin/info/properties:/admin/info/keyPermissionBypassVulnerability(CVE-2024-45216)CVSScore:7.3漏洞描述:ApacheSolr是一个开源搜索服......
  • 国产化基于 Zynq-7100 的高性能计算模块FMC载板
    国产化基于Zynq-7100的高性能计算模块FMC载板是一款高性能计算模块。主控芯片采用Xilinx公司Zynq-7系列SoC家族中的XC7Z100-2FFG900(兼容XC7Z045-2FFG900,国产FMQL45T900,和XC7Z035-2FFG900)。其内含ARM公司的Cortex-A9MPCore处理器系统与Xilinx的K......