可以的话看一下最后的总结
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含两个整数 x 和 c。
再接下来 m 行,每行包含两个整数 l 和 r。
输出格式
共 m 行,每行输出一个询问中所求的区间内数字和。
数据范围
−10^9≤x≤10^9,
1≤n,m≤10^5,
−10^9≤l≤r≤10^9,
−10000≤c≤10000
分析
1、从题目所给的数据区间来看,这道题目不可能创建这么长的数组
2、区间求和考虑前缀和 sum[l,r] = s[r] - s[l - 1]
3、由于数列无限长,所以题目中所给出的位置/下标 x l r
必须映射到一个新的变量 y
4、问题重点是如何映射:
4.1、映射的方法有很多种,取定一个规则即可,本题目使用二分 find(x) –> y
4.2、对于 x,c 也就是 a[x] + c
,首先
x-->y
,并且c要关联到x/y上,也就是需要用到一个容器存放<x,c>
,这里采用pair<int,int>
,
你也可以联想到map<>
用处是一样的。
到此符号规定:
vector<pair> add: add
保存的是x,c 这一对,表示添加操作【先保存,后面再进行操作】
vector<int> query: query
保存的是l,r 这一对,表示查询操作【先保存,后面再进行操作】
vector<int> alls: alls
保存是所给下标x l r
接4.2:
输入x,c后
add.push_back({x,c}); // 添加操作
alls.push_back(x); // 需要映射的下标x
4.3、接下来就是输入查询区间[l , r]
同样的,先保存[l , r]
这一对操作,然后保存l r 这两个需要映射的下标
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
4.4、我们知道alls中保存的是需要映射到y的下标x l r
,首先这些下标有可能会重复,进行去重unique
4.5、进行 a[y] + c
的操作
首先当然是find(x) --> y
随后a[y] += c;
这里需要注意的是,该操作放在了add里面,
auto item : add
, item.first == x,item.second == c.
y = item.first;
a[y] += item.second;
4.6、计算前缀和, s[i] = s[i-1] + a[i]
4.7、处理询问操作
首先是取出[l,r] ,然后映射 [l,r] --> [L,R]
s[R] - s[L -1]
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//pair
typedef pair<int,int> PII;
const int N = 300010;
int n,m;
int a[N],s[N];
vector<int> alls;
vector<PII> add,query;
int find(int x){
int l = 0,r = alls.size() - 1;
while(l < r){
int mid = l + r >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1;//映射到 1,2,3...n
}
vector<int>:: iterator unique(vector<int> &a){
int j = 0;
for(int i = 0;i < a.size();i++){
if(!i || a[i] != a[i-1]){
a[j++] = a[i];
}
}
return a.begin() + j;
}
int main(){
cin >> n >> m;
for(int i = 0;i < n;i++){
int x,c;
cin>> x >> c ;
add.push_back({x,c});
alls.push_back(x);
}
for(int i = 0;i < m;i++){
int l,r;
cin>> l >> r ;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
//去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
//添加x
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){
int l = find(item.first), r = find(item.second);
cout<< s[r] - s[l - 1] <<endl;
}
return 0;
}
总结: 其实这道题目就是要把x l r这三个下标映射到y去即可,x 要关联 c,l要关联r