题目描述
题目要求我们计算指定区间和,题意很简单。我们只需要使用前缀和即可。
此题问题是区间的下标过大,−109≤l≤r≤109,为保证数组下标>=0,需要2e9大小,明显不可取。
正解为离散化。
何为离散化?当一组数据很大,而其绝对大小不会影响问题求解,只受相对大小影响时,我们可以把数据“缩小”同时维护其相对大小。
举例:一组数 0 12324 34355549,我们需要求大于0的数据个数时候,我们只需要维护后面的数据比前面大就可以了,至于具体大多少,我们不用管,因为不用求。
故离散化后可为:0 1 2
这样我们把数据规模给降下来了。
离散化3步:
1) 去重。及去除重复元素,可以使用STL中的unique函数。也可以手动实现
n=unique(a,a+n)-a;//n更新为去重后的长度
2)排序。既然要维护相对大小,排序是必不可少的。直接使用STL中sort即可。
sort(a,a+n);
3)离散。也就是说,给一个值,找到离散化后的值。这个其实很简单,我们前面已经把他们排好序了,那么他们的相对大小,不就是他们排序后所在下标吗。直接使用二分查找即可。
//如前面排好序后: 0 12324 34355549,传入x=34355549,返回2,也就是说34355549离散化后值为2
int query(int x) {
return lower_bound(a, a + n, x) - a;
}
此题还需要注意的就是,我们需要先把要加上值的点先存起来,这样才能拿到需要离散化的数据,待离散化后再加上c。还有一些处理细节可看代码。
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 5;
struct node {
int x, c;
} a[N];
int b[N], c[N];
int n, m, k;
//x离散后的值,其实就是下标
int query(int x) {
return lower_bound(b, b + k, x) - b;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
cin >> a[i].x >> a[i].c;
b[i] = a[i].x;
}
k = unique(b, b + n) - b;//k是离散后的总数
sort(b, b + k);
for (int i = 0; i < n; i++) {
int t = query(a[i].x);
c[t] += a[i].c;
}
//前缀和
for (int i = 1; i <=n; i++)
c[i] += c[i - 1];
while (m--) {
int l, r, sum = 0;
scanf("%d%d", &l, &r);
int L = query(l), R = query(r); //L,R对应离散化后的区间
//举个例子,离散前是400 500,现在来了个450。但是query(450)返回值是0,
//不进行特判的话,会把400所在值加上。
while(l>b[L]&&L<k) L++;
while(r<b[R]&&R>=0) R--;
//R>=L保证是有效区间
printf("%d\n",R>=L?c[R]-c[L-1]:0);
}
return 0;
}
zhou_pig yyds
大佬你那步处理得太细节了,顿悟的感觉真好
谢谢你的鼓励。
太强了大佬,大佬能不能带带我
金牌爷说笑了。