题解

思路推导

将每个互不相识的朋友对规范化为 $x<y$。固定区间右端点 $r$，若某个禁配对满足 $y\le r$，那么区间左端点必须大于 $x$，否则该对会同时落入区间。

因此，对每个 $r$ 只需知道所有已经激活的禁配对中最大的较小端点。这个限制随 $r$ 增大只会单调右移。

做法

对每个较大端点 $y$，记录与它配对的所有较小端点中的最大值 ban[y]。从左到右枚举右端点 $r$，维护当前合法区间左端点的最小值 left，令其更新为 max(left,ban[r]+1)。

此时以 $r$ 为右端点的合法区间左端点恰为 left,left+1,...,r，贡献 $r-left+1$。累加所有右端点贡献即可。

正确性证明

扫描到 $r$ 时，left 大于所有较大端点不超过 $r$ 的禁配对的较小端点。因此任意起点不小于 left 的区间都不可能完整包含这些禁配对；较大端点超过 $r$ 的禁配对也不在区间内，所以这些区间全部合法。

若起点小于 left，根据 left 的最后一次更新，存在某个已激活禁配对 $(x,y)$ 满足起点不大于 $x$ 且 $y\le r$，该禁配对完整落入区间，因此区间不合法。故算法对每个右端点计算的贡献准确，累加后得到全部好区间数。

复杂度分析

每个朋友和禁配对只处理常数次，时间复杂度为 $O(n+m)$，空间复杂度为 $O(n)$。