方法一：差分
因为是先修改后查询，很容易想到差分，但因为数据值域 \([-10^9,10^9]\) 过大，所以不能使用差分数组，而应用 map 进行存储，如代码所示：
map<int, int> diff;
// 正常进行差分操作
for(auto& f : flowers) {
diff[f[0]]++;
diff[f[1] + 1]--;
}
// do something
auto it = diff.begin();
int sum = 0;
for(int i : id) {
// 略过了中间的位置
while(it != diff.end() && it->first <= people[i]) {
sum += it++->second;
}
people[i] = sum;
}
注意给出的 \(people\) 数组是无序的，需要 iota 一个 \(id\) 数组，按照 \(people\) 排序。
方法二：二分
分别排序区间的左右端点 \(s,t\)，对每个 \(people_i\) 二分查找前面有多少左端点、右端点，即开花数-凋谢数。
下面是一份 python 代码，非常简练：
class Solution:
def fullBloomFlowers(self, flowers: List[List[int]], people: List[int]) -> List[int]:
starts = sorted(s for s, _ in flowers)
ends = sorted(e for _, e in flowers)
return [bisect_right(starts, p) - bisect_left(ends, p) for p in people]
THE END
参考：灵茶山艾府 https://leetcode.cn/problems/number-of-flowers-in-full-bloom/