【彩色矩形题解】
关键词： 分治，线段树
首先，如果我们能选出3个不同颜色的点就能确定一个矩形。
现在考虑如何选择出3个不同的点。
首先我们先把所有的点对于x从小到大排序，顺便把y给离散化。
我们先假定我们选出来的三个点从左到右的颜色分别为0,1,2
（对于更一般的颜色排列情况，可以使用全排列来解决。）
所以我们可以用"颜色1”来链接1和2。“颜色1”现在是中间值（这只是我们假定的）。假设当前点为i我们定义sonl[i]中存储是左边在y上最接近的比y[i]小的坐标。zsonl[i]中存储所有左边在y上最接近的比y[i]大的坐标。同理有sonl[i],zsonl[i]。
void cdq(int l, int r){
if(r-l+1<3)return;
int mid = l + r >> 1;
cdq(l,mid);cdq(mid+1,r);
set<pair<int,int>> s;
for(int i = mid;i >= l;i --){
if(col[a[i].c] == 1) s.insert({a[i].y, i});
else if(col[a[i].c] == 0){
auto it = s.lower_bound({a[i].y, 0});
// 当前点比最近的1低
if(it != s.end()) sonl[it->second].push_back(i);
// 当前的点比最近的1高
if(it != s.begin()) zsonl[prev(it)->second].push_back(i);
}
}
s.clear();
for(int i = mid + 1;i <= r;i ++){
if(col[a[i].c] == 1) s.insert({a[i].y, i});
else if(col[a[i].c] == 2){
auto it = s.lower_bound({a[i].y, 0});
// 当前点比最近的1低
if(it != s.end()) sonr[it->second].push_back(i);
// 当前的点比最近的1高
if(it != s.begin()){
zsonr[prev(it)->second].push_back(i);
}
}
}
}
这里为什么要用分治来找到每个点最近的不同颜色的点。
因为对于一些中间点来说，它左右两边的候选点可能会被更远的点挡住或替换，从而漏掉更近、但在小区间内才能被枚举的组合。
现在我们有了左右在y上最接近的点。我们的答案就是考虑所有的中间点，让左右两边的点配对，然后计算答案。
对于三个点的，我们显然有四种情况，分别是单调增，单调减，先增后减，先减后增。但是我们可以发现单调减和先减后增，其实是可以关于x轴对称之后变成单调增和单调减的。所以我们本质上只有单调增和先增后减这两种情况。其他的情况可以通过各种关于坐标轴对称来解决。
现在我们仅需考虑如何解决单调增和先增后减如何解决。
对于每一个中间点（“颜色1”），有y[i],我们假定左边点L，右边点R满足y[L] < y[i] < y[R] 或者y[L] < y[i] > y[R]。其中对于第二种情况又有y[L] < y[R] 和y[L] > y[R]。哦，还有y[L] > y[i]的情况，大家自己手玩一下。易得不同情况的计算公式。
现在只考虑当前点和点R（相当于已知两个点，对一串点的贡献求最小值）。对于左边点的贡献我们可以用线段树来得到。我们对于左边点不同的贡献形式，可以创建不同的线段树，以每个点的高度为下标，贡献为值。对于每一个线段树实现单点修改和区间最小值（因为答案要最小）。同理需要倒着考虑一遍，就做完了。 