想要使第i个矩形覆盖第j个矩形，必须满足：
- $i > j$
- $x1_i \le x2_j$ && $x1_j \le x2_i$
- $y1_i \le y2_j$ && $y1_j \le y1_i$
第一个条件可以直接排序。
考虑使用cdq分治完成第二个条件：假设现在维护的区间是$[l,r]$，那么将$[l,mid]$的区间按$x1$从小到大排序，将$[mid+1,r]$的区间按$x2$从小到大排序，即可维护出第二个条件的前半个。
如果剩下的条件还是分开处理，估计就很难写了。所以有一种思路就是将剩下条件巧妙地一步完成。考虑对于第$j$个矩形，只要存在任何一个矩形$i$在满足第一个条件和第二个条件的前半个并且纵坐标与第$j$个矩形有重合部分，并且满足$x1_j \le x2_i$那么第$j$个矩形就被第$i$个矩形覆盖。所以用线段树维护区间最大值，每次将$[y1_i,y2_i]$区间的对$x2_i$取$max$。然后判断第$j$个是否被覆盖的依据是$f_j|=[query(1,y1_j,y2_j) \ge x1_j]$。
标签：y2,le,anje,Sun,x1,x2,2019,y1,矩形 From： https://www.cnblogs.com/nebula-xy/p/17001845.html