AcWing 802. 区间和
2024-09-05 21:19:49
(https://www.acwing.com/problem/content/804/)
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
近下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
思路:离散化+前缀和
由于坐标的数据范围很大,那么将坐标离散化。排序去重后的新下标就是坐标离散化后的坐标。
#include <iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 3e5+;
typedef pair<int,int> pll;
int a[maxn];
int s[maxn];
vector<pll> add,qu;
vector<int> adds;
int find1(int x)
{
int l=,r=adds.size()-;
while(l<r)
{
int mid=l+r >> ;
if(adds[mid]>=x) r=mid;
else l=mid+;
}
return r+;
}
int main()
{
std::ios::sync_with_stdio(false);
int n,m;
cin >> n >> m;
for(int i=;i<=n;i++)
{
int x,y;
cin >> x >> y;
add.push_back({x,y});
adds.push_back(x);
}
for(int i=;i<=m;i++)
{
int l,r;
cin >> l >> r;
qu.push_back({l,r});
adds.push_back(l);
adds.push_back(r);
}
sort(adds.begin(),adds.end());
adds.erase(unique(adds.begin(),adds.end()),adds.end());
for(auto i : add)
{
int x=find1(i.first);
a[x]+=i.second;
}
for(int i=;i<=adds.size();i++)
{
s[i]=s[i-]+a[i];
}
for(auto j : qu)
{
int l=find1(j.first),r=find1(j.second);
cout << s[r]-s[l-] << endl;
}
return ;
}
最新文章
- mybatis学习
- Hibernate使用
- loadrunner处理HTTP重定向请求
- Transform组件C#游戏开发快速入门
- HDU 5009 Paint Pearls 双向链表优化DP
- Winform 关于委托与Invoke和Begin Invoke的使用
- Hibernate中openSession() 与 getCurrentSession()的区别
- Java中的栈:java.util.Stack类
- div a块状布局
- UVA 12219 Common Subexpression Elimination
- OC 中的block使用
- Monotonicity 2[POI2010]
- or1200处理器的异常处理类指令介绍
- mysql-冗余和重复索引
- Java四种引用--《深入理解Java虚拟机》学习笔记及个人理解(四)
- centos7 把终端显示改为英文/中文
- ADC_DMA_TIM
- How to split DMG on macOS
- UVA-315 无向图求割点个数
- sql 思路