QOJ.ac

QOJ

Time Limit: 6 s Memory Limit: 512 MB

# 1838. Intellectual Implementation

Statistics

题解 by @ezoilearner,你可以通过以下联系方式联系作者:

  • QQ: 2939863838

题意:给定若干个长方形,即四元组 $l_i,r_i,d_i,u_i$ 来表示,表示 ${(x,y)|l_i\leq x\leq r_i,d_i\leq y \leq u_i}$ .

问有几个三元组 $(i,j,k)$ ,满足 $(i,j),(j,k),(i,k)$ 没有交。

题解:反向考虑,如果两个点有交,连边。

求出下面两个量即可统计有多少个三元组的生成子图没有边。

1 每个点的度数 2 有多少个 $(i,j,k)$ 两两有边。

难度在 $2$ ,相当于要求两维都有交。$1$差不多

经典办法扩展:考虑有交的话在左下角进行统计

$Ans$ 为 $\sum \binom{含(x,y)的点的个数}{3}-\sum \binom{含(x,y)(x,y+1)的点的个数}{3}-\sum \binom{含(x,y)(x,y+1)点的个数}{3}+\sum \binom{含(x,y)(x+1,y)(x,y+1)(x+1,y+1)点的个数}{3}$ .

扫描线加线段树维护就好了。