思路
- 这道题会在x处+c,搜索l~r的和,故使用到了l,r,x位置,需要把这三个位置映射到正常大小的数组中,记录lr询问
- 我们将x和c的值用键值对vector存下; l,r,x用push进入alls vector ,alls排序去重以保证所有下标不重复;
- 执行x+c的操作时,每次查询x在alls中的位置,然后依次在数组A中赋值+c,
- 在A中建立前缀和,为了对付查询,l,r的位置现在被映射到alls中,故查l~r需要从alls中找对应下标,然后在前缀和数组中计算.
alls不用去重也可以,因为重复的地方在前缀和中是0,不影响结果
代码
/*
* @Author: ACCXavier
* @Date: 2020-11-08 10:43:56
* @LastEditTime: 2021-05-11 00:40:22
* Bilibili:https://space.bilibili.com/7469540
* 题目地址:https://www.acwing.com/problem/content/804/
* @keywords: 区间和
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含两个整数 x 和 c。
再接下来 m 行,每行包含两个整数 l 和 r。
输出格式
共 m 行,每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
*/
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 3e5 + 10;
typedef pair<int, int> PII;
int n, m;
vector<PII> add, query;
vector<int> alls;
int s[N];
void qsort(vector<int> &a, int l, int r) {
if (l >= r) return;
int mid = a[l + r >> 1], i = l - 1, j = r + 1;
while (i < j) {
do i++;
while (a[i] < mid);
do j--;
while (a[j] > mid);
if (i < j) {
swap(a[i], a[j]);
}
}
qsort(a, l, j);
qsort(a, j + 1, r);
}
//要先排好序
vector<int>::iterator unique(vector<int> &a) {
int i, j;
for (i = 0, j = 0; i < a.size(); ++i) {
if (!i || a[i] > a[i - 1]) {
a[j++] = a[i];
}
}
return a.begin() + j;
}
int find(int x) {
int l = 0, r = alls.size() - 1, mid;
while (l < r) {
mid = l + r >> 1;
if (alls[mid] >= x)
r = mid; //必须是a[mid]>=x
else
l = mid + 1;
}
return r + 1;
}
int main() {
scanf("%d%d", &n, &m);
int x, c, l, r;
for (int i = 0; i < n; ++i) {
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; ++i) {
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
//下标离散化 目前下标已经被排好序
qsort(alls, 0, alls.size() - 1);
//sort(alls.begin(),alls.end());
alls.erase(unique(alls), alls.end());
//处理输入
for (int i = 1; i <= n; ++i) {
int x = find(add[i - 1].first);
s[x] += add[i - 1].second;
}
for (int i = 1; i <= alls.size(); ++i) {
s[i] += s[i - 1];
}
//输出
for (auto item : query) {
int l = find(item.first), r = find(item.second);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}