免费的网站程序,55g游戏网,青岛快速排名优化,安徽建设厅网站打不开AcWing 802. 区间和
离散化就是使用更少的下标来表示一部份数// 例如#xff1a;1#xff0c;3#xff0c;5 // 离散化前#xff1a;0#xff0c;1#xff0c;2#xff0c;3#xff0c;4#xff0c;5 // 离散化后#xff1a;0#xff0c;1#xff0c;2注意去重方法…AcWing 802. 区间和
离散化就是使用更少的下标来表示一部份数// 例如135 // 离散化前012345 // 离散化后012注意去重方法先排序在去重sort, unique, erase
#include iostream
#include vector
#include algorithm
using namespace std;const int N 3*(1e5 10);
int a[N];vectorint index_map;
vectorpairint, int add, qry;int find_index(int key)
{int l 0, r index_map.size() - 1;while(l r){int mid (r - l) / 2 l 1;if(index_map[mid] key)r mid - 1;elsel mid;}// 返回值1意为在头部预留一个位置方便处理前缀和return l 1;
}int main()
{int m, n;cin m n;int x, c;for(int i 0; i m; i){cin x c;index_map.push_back(x);add.push_back(make_pair(x, c));}// index_map的作用是压缩元素下标即离散化// 例如135// 离散化前012345// 离散化后012// 因为不涉及加c的位置都是0所以离散化后不影响查询区间和// 离散化使元素个数从可能的 10^9 压缩到 n和m的范围 10^5int l, r;for(int i 0; i n; i){cin l r;qry.push_back(make_pair(l, r));index_map.push_back(l);index_map.push_back(r);}// 先排序再去重index_map下标就是每个加c和查询的位置sort(index_map.begin(), index_map.end());index_map.erase(unique(index_map.begin(), index_map.end()), index_map.end());// 相应位置加c// 离散化后的下标与 10^5 量级的 a[N] 一一对应// 因为 index_map 中已经有序故通过二分查找下标进行加cfor(auto p : add){int micro_index find_index(p.first);a[micro_index] p.second;}// 查询前处理前缀和for(int i 1; i index_map.size(); i){a[i] a[i - 1] a[i];}// 查询for(auto p : qry){int x1 find_index(p.first), x2 find_index(p.second);cout a[x2] - a[x1 - 1] endl;}return 0;
}
