题意：在一个 的矩阵中有
个点，求至少含有
个点的子矩阵个数。
，，时限 。
首先有一个经典的 做法 ：
枚举上下边界 ，从左到右枚举左边界 ，可能的右边界范围在 内，且 是单调右移的，利用二维前缀和不难 判定。
考虑到本题中
较小，也可以用基于点的做法。
若行 之间 右侧的第 近点为 （以 为第一关键字， 为第二关键字），则可能的右边界个数即为
。其中 部分是常数，只需统计 的贡献和。
对于关键点 ，记以它为右侧第 近点的左边界有 个，则贡献为 。
（为了处理边界情况，需要在两侧各预先加入 个边界点）
接下来考虑先枚举上边界，下边界从上到下移动，相当于每次加入一行的点。动态维护所有关键点的
。
对每个关键点 ，设左侧第 近点的横坐标为 ，则范围 内的左边界与 之间产生贡献。
当插入点
时，只会影响该点右侧的
个点，可以暴力更新 。
然后找到该点左侧的
个点，计算自己的贡献。
可以 std::set 维护并使用迭代器访问，复杂度为 ，且常数较大，难以通过。
考虑将过程反过来，将下边界从下向上移动，此时只需要删点。用双向链表维护，删除某个点容易做到
。
删除一个点后，可能影响的也只有右侧的 个点，线性遍历即可。
此时的复杂度即为 。