区间和题解
我觉得如果学习过前缀和,差分这样的知识点的话,理解起来就会轻松很多
我的想象:
题目中数轴的每一个坐标上,都摞着一堆堆“碟子”,其实就是在这个坐标上增加的数,一个叠一个像是很多碟子。对于题目中的数轴,根本不可能开到$2*10^{9}$这个规模的整数数组来记录下他的状态(内存超限)。不如换一下思路:我们要找出输入的每一个区间里,有多少 盘子
于是乎就只需要考虑给出的n次操作。对于每一次操作。记录下 盘子 放在哪个 地方,之后再根据之后m次操作考察在这个区间之中有多少“盘子”。
第一代代码:两层循环,超时是显然的。$O(nm)$,过了12/14
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int n,m;
PII a[100010];
int main()
{
scanf("%d%d", &n,&m);
for (int i = 1; i <= n; i ++ )scanf("%d%d",&(a[i].x),&(a[i].y));
int l,r;
while(m--)
{
scanf("%d%d",&l,&r);
int sum=0;
for(int i=1;i<=n;i++)
{
if(a[i].x>=l && a[i].x<=r)sum+=a[i].y;//考察每一摞“盘子”的位置是否在区间里
}
printf("%d\n",sum);
}
return 0;
}
第二代:
优化思想:
为什么不能够把求解区间里有多少盘子这个过程优化成常数或者是对数级别?
这种区间求和的形式让我们联想到了前缀和/差分。
我们通过上面的分析,知道了可以使用盘子的位置来代替原有的“坐标”,即数组下标从1到n,对应了一个巨长的数轴之中$-10^{9}<=x<=10^{9}$之中离散分布的一堆数,这也就是离散化的重要思想
所以说我们可以对输进去的数组进行整理,让其中的每个下标对应的“坐标”按照一定的顺序排布,使得我们可以更好判断出哪一些坐标在题目给出的区间里边。因为区间是$l<=r$,符合一个递增的关系。所以说我们对应的“坐标”也应该排成这种关系才可以更好进行操作——比如说用前缀和求出从l到r的坐标上一共有几个“盘子”。
同时因为是排序之后的“坐标”单调递增,我们可以使用二分查找优化我们查找区间对应下标的时间。(这里要注意排除下标1到n对应的坐标都没有出现的区间)
最后大吉大利,今晚AC,时间复杂度:$O(m*log(n))$
#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
int n,m;
long long s[100010];
PII a[100010];
bool cmp(PII a,PII b)
{
return a.x<b.x;
}
int main()
{
scanf("%d%d", &n,&m);
for (int i = 1; i <= n; i ++ )scanf("%d%d",&(a[i].x),&(a[i].y));
sort(a+1,a+n+1,cmp);//按照“盘子”的坐标进行升序排序
for (int i = 1; i <= n; i ++ )s[i]=(long long)a[i].y,s[i]+=s[i-1];//先求个前缀和数组
int left,right;
while(m--)
{
scanf("%d%d",&left,&right);
if(left>a[n].x || right<a[1].x)
{
printf("%d\n",0);
continue;
}//排除根本就没有加上数字的区间
int l=0,r=n;
while(l<r)
{
int mid=l+r>>1;
if(a[mid].x>=left)r=mid;
else l=mid+1;
}
int le=l;
l=0,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(a[mid].x<=right)l=mid;
else r=mid-1;
}
int re=r;
//两次二分查找左右端点
long long sum=0;
sum=s[re]-s[le-1];//前缀和一步到位
printf("%lld\n",sum);
}
return 0;
}