汉口专业网站推广公司,国外什么网站是做外贸,微信怎么开公众号,seo技术交流论坛题目 假定有一个无限长的数轴#xff0c;数轴上每个坐标上的数都是 0。 现在#xff0c;我们首先进行 n 次操作#xff0c;每次操作将某一位置 x 上的数加 c。 接下来#xff0c;进行 m 次询问#xff0c;每个询问包含两个整数 l 和 r#xff0c;你需要求出在区间 [l,r] …题目 假定有一个无限长的数轴数轴上每个坐标上的数都是 0。 现在我们首先进行 n 次操作每次操作将某一位置 x 上的数加 c。 接下来进行 m 次询问每个询问包含两个整数 l 和 r你需要求出在区间 [l,r] 之间的所有数的和。 输入格式 第一行包含两个整数 n 和 m。 接下来 n 行每行包含两个整数 x 和 c。 再接下来 m 行每行包含两个整数 l 和 r。 输出格式 共 m 行每行输出一个询问中所求的区间内数字和。 数据范围 −109≤x≤109 1≤n,m≤105 −109≤l≤r≤109 −10000≤c≤10000 输入样例 3 3 1 2 3 6 7 5 1 3 4 6 7 8 输出样例 8 0 5 来源acwing算法基础 802. 区间和 思路注意事项
N初始化为3e5 10 是因为操作最大1e5次查询 2 * 1e5次。 纯代码
#includebits/stdc.h
using namespace std;
const int N 3e5 10;
int a[N], alls[N];
vectorint all;
vectorpairint,int add, query;int find (int x)
{int l 0, r all.size() - 1;while (l r){int mid l r 1;if (all[mid] x) r mid;else l mid 1;}return r 1;
}
int main()
{int n, m;cin n m;while (n -- ){int x, c;scanf (%d %d, x, c);all.push_back(x);add.push_back({x, c});}while (m --){int l, r;scanf (%d %d, l, r);query.push_back({l, r});all.push_back(l);all.push_back(r);}sort (all.begin(), all.end()); all.erase (unique (all.begin(), all.end()), all.end());for (auto i : add){int t find (i.first);a[t] i.second;}for (int i 1; i all.size(); i ) // 前缀和 alls[i] alls[i - 1] a[i];for (auto i : query){int a find (i.first), b find (i.second);cout alls[b] - alls[a - 1] endl;}return 0;
}题解带注释
#includebits/stdc.h
using namespace std;const int N 3e5 10; // 定义常量N表示最大数据范围
int a[N], alls[N]; // a数组存储离散化后的值alls数组存储前缀和
vectorint all; // all存储所有需要离散化的值
vectorpairint, int add, query; // add存储操作query存储查询// 二分查找函数在离散化后的数组all中查找x的位置并返回其在alls数组中的下标从1开始
int find(int x)
{int l 0, r all.size() - 1; // 初始化左右边界while (l r){int mid l r 1; // 取中间位置if (all[mid] x) r mid; // 如果中间值大于等于x缩小右边界else l mid 1; // 否则缩小左边界}return r 1; // 返回下标从1开始
}int main()
{int n, m;cin n m; // 输入n和m表示操作次数和查询次数// 处理n个操作while (n--){int x, c;scanf(%d%d, x, c); // 输入x和call.push_back(x); // 将x存入all数组add.push_back({x, c}); // 将操作存入add数组}// 处理m个查询while (m--){int l, r;scanf(%d%d, l, r); // 输入l和rquery.push_back({l, r}); // 将查询存入query数组all.push_back(l); // 将l存入all数组all.push_back(r); // 将r存入all数组}// 离散化处理sort(all.begin(), all.end()); // 对all数组排序all.erase(unique(all.begin(), all.end()), all.end()); // 去重// 处理操作for (auto i : add){int t find(i.first); // 找到x离散化后的位置a[t] i.second; // 在a数组中累加c}// 计算前缀和for (int i 1; i all.size(); i) // 遍历alls数组alls[i] alls[i - 1] a[i]; // 计算前缀和// 处理查询for (auto i : query){int a find(i.first), b find(i.second); // 找到l和r离散化后的位置cout alls[b] - alls[a - 1] endl; // 输出区间和}return 0; // 程序结束
}
