````
开始
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;//这步是1 2 3 4 5 6
else l = mid + 1; // 6 8 11 21 30 78 在六个数的范围里二分,找到了直接返回如 找9 //没找到就是9,9对应数值就是0
} // 找11 //在六个数范围里二分,找到了返回11,所对应下标就是11;下面的a[x],都已经加完了
return r + 1;
}
int main()
{
cin >> n >> m;//根据题目要求在指定位置 增加指定数,由此使用一重循环
for (int i = 0; i < n; i ++ )
{
int x, c;
cin >> x >> c;//add,是新开的二维数组
add.push_back({x, c});//这是二维数组例如a[x][y],x对应x,y对应c,大概想法是[x1][x2][x3][x4] 不要想当然说x1,和x2中间有数值连续(非顺序)
// [c] [c] [c] [c]
alls.push_back(x);//新开的一维数组,储存题目要求指定位置 如x1,x2,
}
for (int i = 0; i < m; i ++ )//题目要求输入l,r,求这两个数字之间区间的和,用一重循环
{
int l, r;
cin >> l >> r;
query.push_back({l, r});//新开的二维数组,储存l,r,与上面描述的大概想法一样,
alls.push_back(l);
alls.push_back(r);//这个时候这个一维数组已经有x,l,r,的值了,可能会重复,现在脑中幻想这三条线。
}
// 去重,
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());//排序后注意这并不是顺序123456,而是有序的从小到大
// 处理插入
for (auto item : add)//是二维数组,把它理解为双重循环,例如a[x][y] item.first是对应x,item.second对应y
{//这个执行的时候,按一重循环来执行。
int x = find(item.first);//注意这是从排完序的有序一维数组长度中查找x对应的位置
a[x] += item.second;//这是指定位置赋值,a[N]是顺序的,
}
// 预处理前缀和
for (int i = 1; i <= 300000; 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;
}
`````