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}$ .
扫描线加线段树维护就好了。
The discussion section is only for posting: Editorials, General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.
This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.
If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.
Guidelines: