同城同镇网站建设,wordpress文章图片轮播,湛江seo哪家好,品牌网站建设小8蝌蚪1.前置知识#xff1a;
unique是 c标准模板库STL中十分实用的函数之一#xff0c;使用此函数需要#include algorithm头文件
该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素。 (1) 这里的去除并非真正意义的erase#xff0c;而是将重复的元素放到容…1.前置知识
unique是 c标准模板库STL中十分实用的函数之一使用此函数需要#include algorithm头文件
该函数的作用是“去除”容器或者数组中相邻元素的重复出现的元素。 (1) 这里的去除并非真正意义的erase而是将重复的元素放到容器的末尾返回值是去重之后的尾地址。 (2) unique针对的是相邻元素所以对于顺序顺序错乱的数组成员或者容器成员需要先进行排序可以调用std::sort()函数
2.例题区间和
假定有一个无限长的数轴数轴上每个坐标上的数都是 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
输入样例
3 3
1 2
3 6
7 5
1 3
4 6
7 8输出样例
8
0
5#include iostream
#include vector
#include algorithm
using namespace std;
const int N 300010;
int n, m;
int a[N], s[N]; // a:存离散化后的数 s:存a的前缀和
vectorint alls; // 存原数x
vectorpairint, int adds, query; // 存x,c l,r
int find(int x)
{int l 0, r alls.size() - 1;while (l r){int mid (l r) / 2;if (alls[mid] x)r mid;elsel mid 1;}return r 1; // 映射到从1开始的下标
}
int main()
{cin n m;for (int i 0; i n; i){int x, c;cin x c;adds.push_back({x, c}); // x位置calls.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 it : adds){int x find(it.first);a[x] it.second; // a[]:离散化后}// 预处理前缀和for (int i 1; i alls.size(); i) // 映射到1~alls.size(){s[i] s[i - 1] a[i];}for (auto it : query){ // 处理询问int l find(it.first), r find(it.second); // 取离散化之后的l和rcout s[r] - s[l - 1] endl;}return 0;
}
