题目描述

面向新手（比如我）的Q＆A

样例

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;

typedef pair[HTML_REMOVED] PII;

const int N = 300010;

int n, m;
int a[N], s[N];

vector[HTML_REMOVED] alls;
vector[HTML_REMOVED] 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;
}

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());

// 处理插入
for (auto item : add)
{
    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;

}
```
Q1:为什么要把x，l和r一起存进alls中:
A1：在我刚看样例时，一直不明白x和l，r明明是两种坐标表示，为什么要存在一起。因为我最开始的思路是存分别存x和lr，使用的时候再分别调用。实际上alls存入的是需要使用的下标，也就是在这么长的数轴上需要进行操作的下标，这样每次对数组进行操作的时候就只用调用alls数组就行了。
Q2：为什么要进行去重和排序。
A2：正如A1中所说，alls中存入的是需要调用的下标，我们想要在之后的前缀和中使用这些下标，就需要对这些下标进行排序去重。
Q3：find函数作用
A3：find函数在alls数组中寻找x，并返回x在alls数组中的下标，这样就不用在长数轴中浪费时间一个一个求前缀和，而可以直接把已经进行操作的值（即每个x+1所对应的值）进行前缀和