题目描述：
假定有一个无限长的数轴，数轴上每个坐标上的数都是 $ 0 $ 。
现在，我们首先进行 $ n $ 次操作，每次操作将某一位置 $ x $ 上的数加 $ c $ 。
接下来，进行 $ m $ 次询问，每个询问包含两个整数 $ l $ 和 $ r $ ，你需要求出在区间 $ [l,r] $ 之间的所有数的和。
输入格式
第一行包含两个整数 $ n $ 和 $ m $ 。
接下来 $ n $ 行，每行包含两个整数 $ x $ 和 $ c $ 。
再接下来 $ m $ 行，每行包含两个整数 $ l $ 和 $ r $ 。
输出格式
共 $ m $ 行，每行输出一个询问中所求的区间内数字和。
数据范围
输入样例：
1
2
3
4
5
6
7
| 3 3
1 2
3 6
7 5
1 3
4 6
7 8
|
输出样例：
题解：
很明显是单点加，区间求和。需要使用前缀和。
因为数太大，所以离散化，用 map 存起来，然后求前缀和，最后使用二分查找找到区间左端点和右端点，求出答案
注意可能有重复的，可以使用二分查找到重复的，再加上去，也可以直接 map 完事。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
map<int, int> mp;
vector<PII> a;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1, x, v; i <= n; i++)
{
cin >> x >> v;
if (!mp.count(x))
{
mp[x] = v;
}
else
{
mp[x] += v;
}
}
int tmp = 0;
for (PII kv : mp)
{
a.push_back({kv.first, tmp});
tmp += kv.second;
}
a.push_back({INF, tmp});
int l, r;
while (m--)
{
cin >> l >> r;
auto l1 = lower_bound(a.begin(), a.end(), (PII){l, -INF});
auto r1 = upper_bound(a.begin(), a.end(), (PII){r, INF});
cout << r1->second - l1->second << endl;
}
return 0;
}
|