当前位置:网站首页>Interval sum ----- discretization
Interval sum ----- discretization
2022-07-06 16:03:00 【It's Xiao Zhang, ZSY】
discretization
Satisfy the property of discretization : The range of values is large , Sparse number
a[ ] : { 1 , 3 , 100 , 200 , 500000000 } mapping
Subscript :0 1 2 3 4
1.a[] There may be duplicate elements in duplicate removal
2. How to calculate the discrete value Two points ( This question is in order )
Interval and
Suppose there is an infinite number axis , The number on each coordinate on the number axis is 0. Now? , Let's start with n operations , Each operation will a certain position x Add... To the number on c. Next , Conduct m Time to ask , Each query contains two integers l and r, You need to find the interval [l,r] The sum of all numbers between . Input format : The first line contains two integers n and m. Next n That's ok , Each line contains two integers x and c. Next m That's ok , Each line contains two integers l and r. Output format : common m That's ok , Each line outputs a number in the interval and . Data range −1e9≤x≤1e9,1≤n,m≤1e5,−1e9≤l≤r≤1e9,−10000≤c≤10000
sample input :
3 3
1 2
3 6
7 5
1 3
4 6
7 8
sample output :
8
0
5
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
int const N=3e5+10; // In the array x,l,c Corresponding to the discretized value , The number is the most 3*1e5
int a[N],s[N];
vector<int> lisan; // Store all discretized values
typedef pair<int,int> PII;
vector<PII> addxc,xunwenlr; // Insert x c; Insert query l r;
int find(int x) // Find the result of discretization
{
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; // Coordinate addition 1, Map to from 1 Start ;
}
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()); // duplicate removal , Inserted x l r Remove the same
for(auto item:addxc) // Insert processing
{
int xx=find(item.first); //xx The subscript corresponding to discretization
a[xx]+=item.second;
}
for(int i=1;i<=lisan.size();i++) // The prefix and
s[i]=s[i-1]+a[i];
for(auto item:xunwenlr) // Deal with inquiries
{
l=find(item.first); // The subscript corresponding to discretization
r=find(item.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
// Remove the weight from the top unique Functions and erase function Source code
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() function , The following elements replace the previous repeated elements , Generally, it is used after sorting ( The adjacent elements are removed ), The space behind has not been deleted
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[]={
2,3,4,4,6};
sort(a,a+5); // Generally in use unique It needs to be sorted before ;
unique(a,a+5); // Use unique The array de duplication function
for(int i=0;i<5;i++)
{
cout<<a[i]<<” “; // 2 3 4 6 6
}
cout<<" The length of the non repeating sequence :"<<unique(a,a+5)-a<<endl; // The length of the unrepeated sequence :4
}
边栏推荐
- [exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
- [exercise-6] (PTA) divide and conquer
- HDU - 6024 Building Shops(女生赛)
- Accounting regulations and professional ethics [1]
- 【练习-1】(Uva 673) Parentheses Balance/平衡的括号 (栈stack)
- If you want to apply for a programmer, your resume should be written like this [essence summary]
- MySQL授予用户指定内容的操作权限
- [exercise-4] (UVA 11988) broken keyboard = = (linked list)
- Pyside6 signal, slot
- C语言数组的概念
猜你喜欢
Analyse du format protobuf du rideau en temps réel et du rideau historique de la station B
基于web的照片数码冲印网站
滲透測試 ( 1 ) --- 必備 工具、導航
Nodejs+vue online fresh flower shop sales information system express+mysql
Penetration test (4) -- detailed explanation of meterpreter command
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
PySide6 信号、槽
[exercise-7] crossover answers
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
渗透测试 ( 1 ) --- 必备 工具、导航
随机推荐
Cost accounting [20]
New to redis
Opencv learning log 30 -- histogram equalization
Matlab comprehensive exercise: application in signal and system
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
VS2019初步使用
The most complete programming language online API document
Auto.js入门
Cost accounting [19]
Research Report on market supply and demand and strategy of geosynthetics industry in China
Opencv learning log 16 paperclip count
Accounting regulations and professional ethics [3]
China's salt water membrane market trend report, technological innovation and market forecast
[exercise-1] (UVA 673) parentheses balance/ balanced brackets (stack)
Cost accounting [24]
C语言必背代码大全
Penetration test (3) -- Metasploit framework (MSF)
最全编程语言在线 API 文档
初入Redis
对iptables进行常规操作