当前位置:网站首页>区间和------离散化
区间和------离散化
2022-07-06 09:25:00 【是小张张呀 zsy】
离散化
满足离散化的性质:值域大,数稀疏
a[ ] : { 1 , 3 , 100 , 200 , 500000000 } 映射
下标:0 1 2 3 4
1.a[]中可能有重复的元素 去重
2.如何计算出离散化的值 二分(此题有序)
区间和
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。现在,我们首先进行 n 次操作,每次操作将某一位置 x上的数加 c。接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。输入格式:第一行包含两个整数 n 和 m。接下来 n 行,每行包含两个整数 x 和 c。再接下来 m 行,每行包含两个整数 l 和 r。输出格式:共 m 行,每行输出一个询问中所求的区间内数字和。数据范围−1e9≤x≤1e9,1≤n,m≤1e5,−1e9≤l≤r≤1e9,−10000≤c≤10000
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
int const N=3e5+10; //数组里面存x,l,c对应离散化的值,个数最多3*1e5
int a[N],s[N];
vector<int> lisan; //存入所有离散化的值
typedef pair<int,int> PII;
vector<PII> addxc,xunwenlr; //插入x c; 插入询问l r;
int find(int x) //求离散化的结果
{
int l=0,r=lisan.size()-1;
while(l<r)
{
int mid=l+r >> 1;
if(lisan[mid]>=x) r=mid;
else l=mid+1;
}
return r+1; //坐标加1,映射到从1开始;
}
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
int x,c;
cin>>x>>c;
lisan.push_back(x);
addxc.push_back({
x,c});
}
for(int i=0;i<m;i++)
{
cin>>l>>r;
xunwenlr.push_back({
l,r});
lisan.push_back(l);
lisan.push_back(r);
}
sort(lisan.begin(),lisan.end());
lisan.erase(unique(lisan.begin(),lisan.end()),lisan.end()); //去重,插入的x l r 去掉相同的
for(auto item:addxc) //插入处理
{
int xx=find(item.first); //xx离散化所对应的下标
a[xx]+=item.second;
}
for(int i=1;i<=lisan.size();i++) //前缀和
s[i]=s[i-1]+a[i];
for(auto item:xunwenlr) //处理询问
{
l=find(item.first); //离散化所对应的下标
r=find(item.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
//上面去重unique函数和erase函数 原代码
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];
Return a.begin()+j;
}
unique()函数,后面的元素替换的前面重复的元素,一般排序后使用(去除的是相邻元素),后面的空间并没有删除掉
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[]={
2,3,4,4,6};
sort(a,a+5); //一般在使用unique之前都需要进行排序;
unique(a,a+5); //使用unique函数对数组进行去重
for(int i=0;i<5;i++)
{
cout<<a[i]<<” “; // 2 3 4 6 6
}
cout<<"不重复数列的长度:"<<unique(a,a+5)-a<<endl; //不重复序列的长度:4
}
边栏推荐
- [C language] twenty two steps to understand the function stack frame (pressing the stack, passing parameters, returning, bouncing the stack)
- Future trend and planning of software testing industry
- Accounting regulations and professional ethics [3]
- C语言数组的概念
- JS --- detailed explanation of JS facing objects (VI)
- Eslint--- error: newline required at end of file but not found (EOL last) solution
- Research Report on market supply and demand and strategy of China's Medical Automation Industry
- How to become a good software tester? A secret that most people don't know
- Research Report of pharmaceutical solvent industry - market status analysis and development prospect prediction
- csapp shell lab
猜你喜欢
The most detailed postman interface test tutorial in the whole network. An article meets your needs
Learning record: use stm32f1 watchdog
ucore lab5
Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
Learning record: USART serial communication
JS --- all knowledge of JS objects and built-in objects (III)
C4D quick start tutorial - Introduction to software interface
Crawler series (9): item+pipeline data storage
力扣刷题记录
Do you know the advantages and disadvantages of several open source automated testing frameworks?
随机推荐
LeetCode#36. Effective Sudoku
Research Report on market supply and demand and strategy of Chinese hospital cleaning chemicals industry
Interview answering skills for software testing
TCP的三次握手与四次挥手
Research Report on printed circuit board (PCB) connector industry - market status analysis and development prospect forecast
C4D quick start tutorial - creating models
Cost accounting [13]
C语言是低级和高级的分水岭
UCORE Lab 1 system software startup process
The wechat red envelope cover designed by the object is free! 16888
Your wechat nickname may be betraying you
C4D quick start tutorial - Introduction to software interface
Take you to use wxpy to create your own chat robot (plus wechat interface basic data visualization)
LeetCode#198. raid homes and plunder houses
FSM and I2C experiment report
Leetcode notes - dynamic planning -day6
JDBC introduction
JS --- all knowledge of JS objects and built-in objects (III)
学习记录:理解 SysTick系统定时器,编写延时函数
Learning record: USART serial communication