As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
题解 by @ezoilearner，你可以通过以下联系方式联系作者：
题意:给定若干个长方形，即四元组 $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}$ .
扫描线加线段树维护就好了。
We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.
You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.
STOP! Before you submit an issue, please READ the following guidelines: