AcWing 802. 区间和map + upper_bound()解法
原题链接
简单
作者：
空空如也
,
2020-04-25 22:33:53
,
所有人可见
,
阅读 2676
这里提供一种map + upper_bound()的解法
时间复杂度 O((n + m) * log n)
- 将各个出现过的x映射到map中
- 计算一下前缀和
- upper_bound()查找l与r
C++ 代码
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define pii pair<int, int>
const int inf = 1e9 + 5;
vector<pii> a;
map<int, int> mp;
int main()
{
int n, m;
cin >> n >> m;
while(n --)
{
int x, c;
cin >> x >> c;
if(mp.find(x) == mp.end()) mp[x] = c; //x未出现过
else mp[x] += c; //x出现过
}
int sum = 0;
for(pii x : mp) //计算前缀和
{
a.push_back({x.first, sum}); //这里的sum不包含x.first上的值，方便使用upper_bound()
sum += x.second;
}
a.push_back({inf, sum}); //最后加一个无穷大的点，方便处理
//因为mp是有序的，所以a是有序的
while(m --)
{
int l, r;
cin >> l >> r;
auto p1 = upper_bound(a.begin(), a.end(), (pii){l , -inf}); //找到第一个大于等于l的点
auto p2 = upper_bound(a.begin(), a.end(), (pii){r , inf}); //找到第一个大于r的点
cout << p2 -> second - p1 -> second << endl;
}
return 0;
}
不用区分出没出现过吧，直接加就行，map一个元素就存一次
auto p1 = upper_bound(a.begin(), a.end(), (pii){l , -inf}); //找到第一个大于等于l的点
这里的-inf用得太好了，用-inf进行限制，得以找到第一个大于等于l的点。
STL大法好
能不能问一下upper_bound二分pair的规则啊
pair 默认的比较规则是：先比较第一个数的大小，第一个数小的pair小；如果第一个数相等，再比较第二个数
哦哦谢谢！
那请问lower和upper的规则有什么区别吗，我两个都过了
lower_bound是大于等于，upper_bound是大于
STL大法好！
这层循环可以去掉吧, map定义为全局的,找不到的话返回的值是0 直接mp[x] += c;
老公我说的对吗
太对了！！！
STL大法好+1
STL大法好！！
STL大法好