Rectangles

有点营养的题。 很容易做三条竖线，接下来考虑两竖一横。直接枚举横线会变成支持加入区间删除区间维护有多少种方案选择两个点使得任何区间至少包含其一。当然一个想法是线段树分治，以一只 log 的代价转化为只有加入，这个先放着。胡乱离散化一下，又可以转化为点带权但值域只有 \(2n\)。当然这样会存在线段相 ......

比较抽象的一个题。 首先先考虑 \(T=1\)，如果我们建一张图，将图上所有横线与竖线的交点看作图上的点，相邻的有线段相连的点看作图上的边的话，那么显然会得到一张平面图，而我们要计算的是平面图上面的个数，根据公式 \(F=E-V+C+1\)，其中 \(C\) 为这张图中连通块的个数。设 \(c\) ......

`divide and conquer`，简单分治题。 显然可以做二维前缀和，考虑令矩阵 $(l_x-1,r_x,l_y-1,r_y)\to (l_x,r_x,l_y,r_y)$，方便统计答案，其实就是左端点减一。 考虑现在按照 $x$ 坐标分治，计算所有跨过 $x=\text{mid}$ 的矩形的 ......

给出n个点。问选出4个点作为定点，能够组成多少个平行与坐标轴的矩形。 点按照x排序 n^2挑选出 垂直x轴的线段，按照y1排序 #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namesp ......