当前位置:网站首页>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
}
边栏推荐
- Penetration test (3) -- Metasploit framework (MSF)
- E. Breaking the Wall
- MySQL授予用户指定内容的操作权限
- The most complete programming language online API document
- 区间和------离散化
- Information security - Epic vulnerability log4j vulnerability mechanism and preventive measures
- Perform general operations on iptables
- Accounting regulations and professional ethics [2]
- 程序员的你,有哪些炫技的代码写法?
- Perinatal Software Industry Research Report - market status analysis and development prospect forecast
猜你喜欢
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
差分(一维,二维,三维) 蓝桥杯三体攻击
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
渗透测试 ( 5 ) --- 扫描之王 nmap、渗透测试工具实战技巧合集
C语言数组的概念
Nodejs+vue网上鲜花店销售信息系统express+mysql
b站 实时弹幕和历史弹幕 Protobuf 格式解析
mysql导入数据库报错 [Err] 1273 – Unknown collation: ‘utf8mb4_0900_ai_ci’
【练习-5】(Uva 839)Not so Mobile(天平)
Information security - threat detection - detailed design of NAT log access threat detection platform
随机推荐
【练习-2】(Uva 712) S-Trees (S树)
【练习-8】(Uva 246)10-20-30==模拟
Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
[exercise-8] (UVA 246) 10-20-30== simulation
Accounting regulations and professional ethics [1]
信息安全-史诗级漏洞Log4j的漏洞机理和防范措施
STM32 learning record: LED light flashes (register version)
Cost accounting [21]
【练习-7】(Uva 10976)Fractions Again?!(分数拆分)
Information security - threat detection - detailed design of NAT log access threat detection platform
Cost accounting [24]
China's salt water membrane market trend report, technological innovation and market forecast
【练习4-1】Cake Distribution(分配蛋糕)
Opencv learning log 32 edge extraction
对iptables进行常规操作
Interesting drink
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Research Report on market supply and demand and strategy of China's land incineration plant industry
Shell Scripting
[exercise-9] Zombie's Treasury test