塔子哥拥有一片神秘的花园,花园中种满了奇花异草,每一种植物都有其独特的编号,从 0 到 N。塔子哥为了研究稀有花卉的生长规律,每天都会在园中巡视。最近,他发现有些花卉的生长受到了未知因素的影响。经过观察,塔子哥认为是每晚飞过花园的神秘飞鸟对这些植物造成了一定的影响。
每当夜晚,神秘飞鸟会从一个编号的区域飞到另一个编号的区域。每次飞过,它们都会经过一串连续编号的植物区域,并对这些植物进行神秘的歌唱,从而影响它们的生长。
简化一下题意:给定 m 个区间 [li,ri] ,每次给该区间的所有数加上 1(初始值为0),之后进行 Q 次询问,每次询问坐标 x 的值是多少。
这样转化完之后就变成一维差分数组的板子题了,给 a 数组中的 [l,r] 区间中的每一个数都加上 c,只需对差分数组 b 做 b[l]+=c, b[r+1]−=c。
将差分数组转化为原数组只需对差分数组求前缀和即可。