前缀和
前缀和:
每一个数分别储存它的前面所有的数字之和,用于优化运算速度
注意:前缀和数组的数据范围要足够大
eg:
题目描述
有N条线段,已知每条线段的起点和终点(0500000内的整数),然后有M个询问,每次询问一个点(0500000内的整数),求这个点在多少条线段上出现过?
输入
第一行N线段条数
接下来N行,每行两个数(l,r),线段的起点和终点
第N+2行一个数M询问个数
接下来M行,每行一个点
输出
对于每个询问,求答案
常规会采用for循环,将l,r之间的数在数组上+1,但会超时
本题采用:
var
i,j,n,m,l,r:longint;
a,b:array[0..500000] of longint;
begin
readln(n);
for i:=1 to n do
begin
readln(l,r);
a[l]:=a[l]+1;
a[r+1]:=a[r+1]-1; //+1表示线段起点,-1表示线段终点
end;
b[0]:=a[0]; //可能0是某条线段的起点
for i:=1 to 500000 do
b[i]:=b[i-1]+a[i]; //如果不是起点或终点,则线段数与前一个点相同,起点则+1,终点则-1
readln(m);
for i:=1 to m do
begin
readln(j);
writeln(b[j]); //输出结果
end;
end.
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接:https://hs-blog.axell.top/archives/25/