map + 前缀和
$y总基础课的代码有点冗长,如果喜欢简短一点的可以看下面代码,基本思想是使用map + 前缀和$
$首先使用map将所有用到的坐标进行离散化,map的second记录该数应该放在哪里$
$之后利用前缀和思想求取$
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, q;
int s[N];
PII a[N]; //记录哪个位置加了多少
PII b[N]; //记录询问的每一个区间
map<int, int>m; //使用map进行离散化,map默认从小到大
int main()
{
cin >> n >> q;
//先将每一个用到的坐标加到map里面
for(int i = 0; i < n; i++)
{
cin >> a[i].x >> a[i].y;
m[a[i].x] = 1;
}
for(int i = 0; i < q; i++)
{
cin >> b[i].x >> b[i].y;
m[b[i].x] = 1, m[b[i].y] = 1;
}
int idx = 0;
// map默认是从小到大的顺序
// map的second记录该数按照从小到大的顺序应该放在哪个位置
for(auto &t : m)
{
t.y = ++ idx;
}
// 使用前缀和
// 该数放的位置处加上要加的数
for(int i = 0; i < n; i++)
{
s[m[a[i].x]] += a[i].y;
}
// 前缀和
for(int i = 1; i <= idx; i++) s[i] += s[i-1];
// 根据数字放在哪里进行求取(前缀和思想)
for(int i = 0; i < q; i++)
{
cout << s[m[b[i].y]] - s[m[b[i].x] - 1] << endl;
}
return 0;
}
STL大法好,给大佬点赞。😊
小tips:使用auto修改map中值需要添加引用符号
&
,否则map中的值是不会修改的,相关知识可以查看这篇博客 C++ auto的使用