BIT

感觉是一个很多人用的，但是搜了一圈好像没人写（ 首先是一道题。校内模拟赛的，不知道有没有原（ 在 n \times m 的平面上有 n 个互不相交的矩形（可以看作平面直角坐标系），左下角为 (x_1, y_1)，右上角为 (x_2, y_2)。然后有 q 组询问，每次询问查询给定矩形与平面上每个矩形的面积交的和。 n, m \le 5\times 10^5。 有一个朴素的 O(nm) 的做法，就是差分维护给定的矩形（修改），跑两遍前缀和，第一遍前缀和求出差分数组的原数组，第二遍是为了快速区间求和 […]