企业网站主页素描模板,wordpress 图片问题,seo怎么做优化方案,域名查询万网目录 1.例题2.算法实现思路3.代码 1.例题
假定有一个无限长的数轴#xff0c;数轴上每个坐标上的数都是 0现在#xff0c;我们首先进行 n 次操作#xff0c;每次操作将某一位置 x 上的数加 c接下来#xff0c;进行 m 次询问#xff0c;每个询问包含两个整数 l 和 r#… 目录 1.例题2.算法实现思路3.代码 1.例题
假定有一个无限长的数轴数轴上每个坐标上的数都是 0现在我们首先进行 n 次操作每次操作将某一位置 x 上的数加 c接下来进行 m 次询问每个询问包含两个整数 l 和 r你需要求出在区间 [l,r] 之间的所有数的和。输入格式
第一行包含两个整数 n和 m接下来 n 行每行包含两个整数 x 和 c再接下来 m 行每行包含两个整数 l 和 r输出格式共 m 行每行输出一个询问中所求的区间内数字和。数据范围
−10^9≤x≤10^91≤n,m≤10^5−10^9≤l≤r≤10^9−10000≤c≤100002.算法实现思路
由于数轴是无限长的所以我们无法直接使用前缀和算法来解题但换种思路该题的难点就在于由于数轴无限长所以限制了我们利用前缀和所以我们可以换种思路由于n和m都在10的五次方内所以此题给出的坐标数量最多不超过3*10的五次方个我们就可以由这个数目将每个坐标进行映射然后就可以使用前缀和来求解,离散化就是把大而分散的一段段使用到的稀疏区间整合映射到连续的一段较小的稠密区间里然后就可以通过普通前缀和公式来计算连续一段的区间和本质上就是化大为小把稀疏离散化简为稠密连续的一段。
3.代码
#includebits/stdc.h
using namespace std;
const int N3*1e510;
typedef pairint,intPII;
int a[N],s[N];
vectorPIIadd,get1;
vectorintalls;
int find(int x)
{int l0,ralls.size()-1;while(lr){ int mid(lr)/2;if(alls[mid]x){rmid;}else{lmid1;}}return l1;}
int main()
{int n,m;cinnm;for(int i0;in;i){int x,c;cinxc;add.push_back({x,c});alls.push_back(x);}for(int i0;im;i){int l,r;cinlr;get1.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 xfind(item.first);a[x]item.second;}for(int i1;ialls.size();i){s[i]s[i-1]a[i];}for(auto item:get1){int lfind(item.first);int rfind(item.second);couts[r]-s[l-1]endl;}return 0;
}结尾今天的分享到此结束喜欢的朋友如果感觉有帮助可以点赞三连支持咱们共同进步!
