题面
给定 $2n$ 个线段 $[l_i,r_i]$ $(1 \le i \le n)$ 和 $[s_i,t_i]$ $(1 \le i \le n)$，对于所有排列 $p$ 求 $\bigcup_{i=1}^{n} [l_i,r_i] \times [s_{p_i}, t_{p_i}]$ （面积并）之和。其中 $1 \le n \le 2 \times 10^5$。
分析
拆开来算贡献。
对于第一维（$x$ 轴），将其通过左闭右开区间离散化为小块。假设每块被覆盖了 $s_i$ 次，也就意味着这一个块对应了 $s_i$ 个 $y$ 轴线段。比如说，$s_i=0$，那么上面没有任何线段；$s_i=1$，对应了 $1$ 个线段，也就是所有线段均有可能竖着放在它上面，对答案的总贡献为所有线段的总长度；类似地，$s_i=2$ 就是枚举一对线段计算贡献之和。
可以发现，对于每一个小块只有参数 $s_i$ 有效。于是，我们将问题转化为了一个一维的问题，即对于从线段集合中选择 $k=0,1,\dots,n$ 条线段产生的总贡献，形式化地 $f(k)=\sum_{S \subseteq U, |S|=k} |\bigcup_{i \in S} [s_i, t_i]|$。
再拆开来算一次贡献，同样离散化。假设每块被覆盖了 $s_i$ 次，这个块产生贡献当且仅当选出的 $k$ 个块包含 $s_i$ 中的某一个，即方案数就是 $\binom{n}{k} - \binom{n-s_i}{k}$，对于贡献还要乘上块的长度。观察上面的式子，第一部分是平凡的，关键是第二部分，因为我们最终计算的是 $f(k)$ 每个点的值，因此同样的 $n-s_i$ 产生的长度贡献可以记录在一起。于是，我们定义这部分的贡献函数 $g(k)=\sum_{i=k}^n a_i C(i,k)$，其中 $a_i$ 就是长度和。
将 $g$ 展开
$$
\begin{eqnarray}
g(k) & = & \sum_{i = k}^n a_i \frac{i!}{k!(i-k)!} \
g(k) & = & \frac{1}{k!} \sum_{i = k}^{n} (a_i \cdot i!) \times \frac{1}{(i-k)!}
\end{eqnarray}
$$
注意到上式的下标分别为 $i$ 和 $i-k$，即差为定值 $k$，使用 FFT 计算即可。
最后，还有一点小问题，$f(k)$ 的贡献是无序的。它表示从第二个集合中选择了 $k$ 条线段去和横轴某一小块的 $k$ 次覆盖对应，剩余随便，也就是需要乘上两部分内部的排列，即 $k! \times (n-k)!$。
