题解：CF2014D Robert Hood and Mrs Hood

· · 题解

考虑暴力，问题转化为求所有区间内工作的数量。

于是规约为下面的数据结构问题：

插入一个区间 [l,r] ，或查询一个区间与之前多少个区间有交集。

然后这个问题就是 这题 的弱化版，我们统计出一个区间前面有多少个左端点，后面有多少个右端点，显然中间的部分就是答案，开两个树状数组维护即可。

时间复杂度 \mathcal{O}(n\log{n}) ，可以通过。

提交记录