题目描述
假定有一个无限长的数轴，数轴上每个坐标上的数都是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
算法
- 定义： 把一个值域很大的范围，映射成一个较小的范围（因为有很多没有用到的坐标）
- 离散化：
第一步，排序后去重。
第二步，求离散化后的坐标值，用二分做。
（思路就是视频讲的，具体都在代码注释里面）
没有unique（去重）函数的，可以参考这个实现：
不重复元素满足这两个性质
//返回的是一个迭代器，双指针算法
/*
第一个指针j是遍历所有的数，第二个指针是指向当前存到了第几个不同的数
*/
vector<int>::iterator unique(vector<int> &a)
{
int j = 0;
for (int i = 0; i < a.size(); i ++ )
//若不满足上述途中的两个性质， ！i是第一个数
if (!i || a[i] != a[i - 1])
//把当前这个数付给前面，j指针再往后走
a[j ++ ] = a[i];
// a[0] ~ a[j - 1] 所有a中不重复的数
//这样就是从0到j这个位置的就是所有不同的数。
return a.begin() + j;
}
参考文献
y总讲解视频
Java
/**
* 数据范围比较小，可以选用前缀和。
* 本题范围较大，考虑一下离散化,本题范围是（-10^9 , 10^9）,但是最多用到30w（n+2m）个坐标。
* 把用到的坐标排序映射到从0开始的
* （当然也有其他的做法）
*/
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;
public class Main{
public static int N = 300010;
// a存储数的 s前缀和数组
public static int[] a = new int[N];
public static int[] s = new int[N];
// alls存所有要离散化的值
public static List<Integer> alls = new ArrayList<>();
// 操作数组：add 添加一个数 query查询
public static List<PII> add = new ArrayList<>();
public static List<PII> query = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader( new InputStreamReader( System.in) );
String[] str = br.readLine().split(" ");
int n = toInt(str[0]) , m = toInt(str[1]);
for( int i = 0 ; i < n ; i++ ){
str = br.readLine().split(" ");
int x = toInt(str[0]) , c = toInt(str[1]);
// 在下标x的位置处加上c 存入add数组
add.add( new PII(x , c) );
// 存入要离散化的下标
alls.add( x );
}
for( int i = 0 ; i < m ; i++ ){
str = br.readLine().split(" ");
int l = toInt(str[0]) , r = toInt(str[1]);
// 存入query数组，要查询的范围
query.add( new PII( l , r ) );
// 存入要离散化的查询下标
alls.add( l );
alls.add(r);
}
// 去重：1.排序 2.去除重复元素
Collections.sort( alls );
int unique = unique( alls );
alls = alls.subList( 0 , unique );
// 处理在离散化之后坐标上加上值
for( PII item : add ){
// 离散化之后的下标
int x = find( item.first , alls );
a[x] += item.second;
}
// 预处理前缀和（这里映射到（1，size））
for( int i = 1 ; i <= alls.size() ; i++ ) s[i] = s[i - 1] + a[i];
// 处理m个询问
for( PII item : query ){
int l = find( item.first , alls ) , r = find( item.second , alls );
System.out.println( s[r] - s[l - 1] );
}
}
// 找到离散化之后的x的下标
public static int find( int x , List<Integer> alls ){
int l = 0 , r = alls.size() -1;
while( l < r ){
int mid = l + r >> 1;
if(alls.get(mid) >= x ) r = mid;
else l = mid + 1;
}
//映射到从1开始的自然数，因为这道题会用到前缀和，所用从1开始，减少一些边界情况
return r + 1;
}
// 双指针：去除重复元素，也就是返回一段不重复元素的下标
public static int unique( List<Integer> list ){
int j = 0;
// i遍历所有的数 j保存的是当前存到了哪个数（j<= i）
for( int i = 0 ; i < list.size() ; i++){
// 满足：当前是第一个数 ；当前数和上一个数不等。 那就把当前位置的数换成不重复的j
if( i == 0 || list.get(i) != list.get( i - 1 ) ){
list.set( j++ , list.get(i) );
}
// 前后两个数相等，i指针往后走，j不动
}
// for结束之后从（0，j-1）就是所有不重复的元素了
return j;
}
public static int toInt(String str){
return Integer.parseInt( str );
}
}
// PII要操作的数据类型
class PII implements Comparable<PII> {
// 这里为了方便就不设置私有。（如果要求规范一点，还是写个方法他返回比较好）
public int first , second;
// public int getFirst(){
// return first;
// }
// public int getSecond(){
// return second;
// }
public PII( int first , int second ){
this.first = first;
this.second = second;
}
@Override
public int compareTo( PII o ){
return this.first - o.first;
}
}
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
//pair存储每个操作
typedef pair<int,int> PII;
/*
因为共n个操作，m次询问，而每次询问都是有两个边界坐标，n和m都是在（1，10^5)这个
范围内，所以总共的规模是n + 2m,也就是30万。
10是多开的，防止边界问题
*/
const int N = 300010;
//a 是存储题目给定的数 s是前缀和
int a[N], s[N];
int n , m;
//vector是所有要离散化的值
vector<int> alls;
//add插入操作 query是求操作
vector<PII> add , query;
//求一下x这个值离散化之后的结果
int find(int x){
//从l——r之间找一个值
int l = 0 , r = alls.size() - 1;
while(l < r){
//mid中点
int mid = l + r >> 1;
//找到大于等于x的最小值
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
//映射到从1开始的自然数，因为这道题会用到前缀和，所用从1开始，减少一些边界情况
return r + 1;
}
int main(){
cin>>n>>m;
for(int i = 0 ; i < n ; i++){
int x , c ;
cin>> x >> c;
//插入操作，在下标x的位置加上c
add.push_back({x,c});
//要把下标x进行离散化，那么就需要把这个x加入到待离散化的数组里面去
alls.push_back(x);
}
//输入进行m次操作
for(int i = 0 ; i < m ; i++){
int l , r;
cin>> l >> r;
query.push_back({l,r});
//l 和 r坐标是需要离散化的，所以也把他们加入到待离散化的数组里面去
alls.push_back(l);
alls.push_back(r);
}//这个时候就已经把所有需要离散化的下标放进了数组。
//下一步就需要对alls数组进行去重
//先排序
sort(alls.begin(),alls.end());
//把重复的元素去掉,unique函数把不重复的元素放在前面重复的放在后面，返
//回不重复元素的最后一个位置
alls.erase(unique(alls.begin(),alls.end()),alls.end());
//分别处理一下两种操作
for(auto item : add){
//首先求一下x这个值离散化之后的结果是多少
int x = find(item.first);
//在离散化之后的坐标上加上要加的数
a[x] += item.second;
}
//预处理一下前缀和
for(int i = 1 ; i <= alls.size() ; i++) s[i] = s[i - 1] + a[i];
//处理询问
for(auto item : query){
//左边是item.first离散化之后的结果,item.first存的是左区间
//r同理
int l = find(item.first) , r = find(item.second);
//中间所有数的个数的和，用前缀和公式来
cout<<s[r] - s[l - 1]<<endl;
}
return 0;
}
