2 条题解
-
0
考虑首先求出前缀和,然后对于每组询问,我们可以用sum[r]-sum[l-1]来得到答案,但是数据下标达到了,没有办法开下数组,于是考虑离散化,将输入的x坐标进行离散,对于查询的区间[l,r],需要找到离散化后的,第一个小于l的值以及离散化后的,第一个小于等于r的值,对于前一个值,可以使用lower_bound找到第一个大于等于l的值再-1,对于后一个,可以使用lower_bound找到第一个大于等于r+1的值再-1。
#include<bits/stdc++.h> using namespace std; const int N = 100010; int n,m,k,s,t,q,b[N],c[N]; struct node{ int x,c; }a[N]; int main() { cin>>n>>q; for (int i=1;i<=n;++i){ cin>>a[i].x>>a[i].c; b[i]=a[i].x; } sort(b+1,b+1+n); m=unique(b+1,b+1+n)-b-1; for (int i=1;i<=n;++i){ c[lower_bound(b+1,b+1+m,a[i].x)-b]+=a[i].c; } for (int i=1;i<=m;++i) c[i]+=c[i-1]; for (int i=1;i<=q;++i){ cin>>s>>t; s=lower_bound(b+1,b+1+m,s)-b-1; t=lower_bound(b+1,b+1+m,t+1)-b-1; cout<<c[t]-c[s]<<"\n"; } }
-
-1
讲解:
首先明确一下题意,先输入两个整数n、m,n代表在区间[-1e9,1e9]某一点加一个整数的次数,输入x c在x处加上c,m代表求某个区间和的次数,输入l r求区间[l,r]的和。
所以此处略作分析,为什么要离散化呢,因为存储的下标实在太大了,如果直接开这么大的数组,根本不现实,第二个原因,本文是数轴,要是采用下标的话,可能存在负值,所以也不能,所以有人可能会提出用哈希表,哈希表可以吗?答案也是不可以的,因为哈希表不能像离散化那样缩小数组的空间,导致我们可能需要从-e9遍历到1e9(此处的含义就是假如我们需要计算1e-9和1e9区间内的值,那我们需要从前到后枚举,无论该值是否存在),因为哈希表不能排序,所以我们一般不能提前知道哪些数轴上的点存在哪些不存在,所以一般是从负的最小值到正的最大值都枚举一遍,时间负责度太高,于是就有了本题的离散化,离散化的本质,是映射,将间隔很大的点,映射到相邻的数组元素中。减少对空间的需求,也减少计算量。
其实映射最大的难点是前后的映射关系,如何能够将不连续的点映射到连续的数组的下标。此处的解决办法就是开辟额外的数组存放原来的数组下标,或者说下标标志,本文是原来上的数轴上的非连续点的横坐标。 此处的做法是是对原来的数轴下标进行排序,再去重,为什么要去重呢,因为本题提前考虑了前缀和的思想,其实很简单,就是我们需要求出的区间内的和的两端断点不一定有元素,提前加如需要求前缀和的两个端点,有利于我们进行二分搜索,其实二分搜索里面我们一般假定有解的,如果没解的话需要特判,所以提前加入了这些元素,从而导致可能出现重复元素。
所以我们将解题步骤主要分为以下五步:
第一首先读入,将每次读入的x c push_back()到add中,将每次读入的位置x push_back()到alls中,将每次读入的l r push_back()到zon中。之后我们对其进行排序去重。去重之后我们进行遍历add,然后在离散化的数组映射到的a数组中进行加上c的操作(用到find函数),后需要初始化s数组,最后我们再次遍历ton,完成求区间[l,r]就可以了。
所以我们这个题最主要的其实就是我们要将之前的点通过映射,映射至一个全新的数轴上,使其在这个全新的数轴上进行一个新的运算。
核心代码
//排序 去重 sort(alls.begin(),alls.end()) ; alls.erase(unique(alls.begin(),alls.end()),alls.end()) ; //初始化 for(auto item:add) { int x = find(item.first) ; a[x]+=item.second ; } //前缀和 for(int i=1; i<=alls.size() ; i++) { s[i] = s[i-1] + a[i] ; } //计算区间和 for(auto item:zon) { int l = find(item.first), r = find(item.second) ; cout << s[r] - s[l-1] <<endl ; }
- 1
信息
- ID
- 71
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 105
- 已通过
- 59
- 上传者