T1：
最大子矩形。n^3降维处理。
T2：
n^2暴力显然。
发现，是曼哈顿距离，不需要一起处理，可以横坐标，纵坐标分开处理。
我的想法是：
1.用两棵线段树，离散化存储每个区间的点的个数，到区间左端点的距离和，到区间右端点的距离和。
2.然后O（n）循环点，每次更新sum值，超过k就break
复杂度理论O(nlogn)但是常数太大卡死。
70pts
正解小常数：
二分一个点mid
每次把1~mid的点按照横（纵）坐标分别排序。
以横坐标为例，x的贡献就是，x*i-sum[i],sum[i]表示，i个点的位置和。
但是，二分里面是nlogn的，总共会卡到nlogn^2还是挂掉。
每次排序太伤了~
所以先在二分外面排一个序，记录每个大小的位置的编号是多少（用一个结构体）。
二分里面，O（n）扫一遍所有的位置，把编号在[1,mid]的数依次取出来，就是一个排序了。
这就相当于在二分里面巧妙的O（n）排序了。
这利用了所有的数都是提前固定给出来的。
所以，总的复杂度是稳定O(nlogn)的。
T3：
手推式子，nlogn优化dp
原文：https://www.cnblogs.com/Miracevin/p/9513161.html