很厉害的数数题。
首先我们自然考虑固定方案如何计算答案。
考虑最左边的区间 \([l_1,r_1]\) 和最右边的区间 \([l_2,r_2]\)，如果有交点，那么所有区间一定都有交点，否则我们计算一下把这两个区间碰到一起需要多少代价，不难发现是 \(l_2-r_1\)，然后删去这两个区间，递归下去。
然后可以自然地得出一个 \(\Theta(n^2)\) 的做法：枚举两个区间，计算这两个区间会被计算到的方案数乘以 \(l_2-r_1\)。
计算方案数是简单的：计算一下左区间左边有多少区间，然后计算一下右区间右边有多少区间，分别设为 \(x,y\)，方案数就是：\(\sum \binom xi \binom yi 2^{n-x-y-2}\)。容易发现可以范德蒙德卷积一下，就变成 \(\binom {x+y}{x} \times 2^{n-x-y-2}\)。
我们将 \(l_i\) 按照递减顺序排序，\(r_i\) 按照递增顺序排序，那么最终答案可以写成：
\[\sum \sum \binom {i+j-2}{i-1} \times 2^{n-i-j} \times (l_j-r_i) \times [l_j>r_i] \]考虑如何优化。
考虑把这个 \(l_j-r_i\) 拆开，变成：
\[\sum \sum \binom {i+j-2}{i-1} \times 2^{n-i-j} \times l_j \times [l_j>r_i]-\sum \sum \binom {i+j-2}{i-1} \times 2^{n-i-j} \times r_i \times [l_j>r_i] \]然后分别计算两部分，不难发现两部分本质相同，我们以计算后面部分为例。
枚举 \(r_i\)，然后计算 \(l_j>r_i\) 的 \(j\) 个数，记为 \(R\)，同时设 \(L=i-1\)。
考虑此时如何计算答案，组合意义一下，我们只需要计算左区间选择数量小于右区间选择数量的方案数，然后再乘上 \(2^{n-L-R-1}\) 即可。
也就是要计算：
\[\sum \sum_{I<J} \binom LI \binom RJ \times 2^{n-L-R-1} \]枚举一下 \(J-I=k\)，变成：
\[\sum_{k=1} \sum \binom LI \binom R{I+k} \]容易发现可以范德蒙德卷积，变成：
\[\sum_{k=1}^R \binom{L+R}{R-k} \]也就是：
\[\sum_{k=0}^{R-1} \binom{L+R}{k} \]我们设 \(F(x,y)=\sum_{k=0}^{y} \binom xy\)，那么现在的问题就是：每次将 \(x\) 或 \(y\) 增加或减少 \(1\)，求出 \(F(x,y)\) 的值。
不难发现由于 \(l_i,r_i \le n\)，并且我们是按顺序枚举的，所以指针移动次数是 \(\Theta(n)\) 级别的，所以我们只需 \(\Theta(1)\) 计算 \(F\) 的变化量即可。
这是经典问题，对于 \(y\) 的变化是容易解决的，对于 \(x\) 的变化则考虑 \(\binom xy=\binom {x-1}{y}+\binom{x-1}{y-1}\)，然后容易推得 \(F(x,y)=2 \times F(x-1,y) - \binom{x-1}{y}\)。
做完了，时间复杂度 \(\Theta(n)\)。
感觉这题最有启发意义是转组合意义那一步。
标签：CF2030G,sum,times,计算,区间,Theta,binom From： https://www.cnblogs.com/tx-lcy/p/18487971