题意：在二维平面上，有 个关键点， 个矩形 ，关键点的权值为 。
给出 个询问，每次询问给定
，对于关键点 ，如果点 在编号在 内的任意一个矩形中，则认为
被区间 的矩形并包含。求区间
的矩形并包含的所有关键点的权值和。
允许离线，，，时限 。
一维子问题：区间线段并权值和
给出序列 和 个区间 。有 个询问，每个询问给出 ，令 ，求 。
离线，序列扫描线，从左到右加入线段，设 为包含 点的编号最大的线段。若加入到第 条线段，可以处理查询 ，则所有 的点都可以贡献。
设 为 的 的和，其区间和即为答案。考虑如何维护
。
每加入一条线段，会使得一个区间的 变成 。经典地，这共会导致
次同色连续段的新建或删除，每次对应一次 的单点修改。
复杂度 。
原问题
我们用 来把矩形拆成
个点的区间。
则一共会有
次区间更新，配合
的分块求和。
复杂度为 。
分块部分可以继续优化，但是由于常数小并没有必要。