这是本文档旧的修订版！
Deltix Round, Summer 2021 (Div. 1 + Div. 2)
E. Equilibrium
题意
给定两个序列 $\{A\},\{B\}$。每次询问一个区间 $[l,r]$。
每次操作可以在 $[l,r]$ 中选择若干对位置 $(a_1,b_1),(a_2,b_2)\cdots (a_k,b_k)$，满足 $a_1\lt b_1\lt a_2\lt b_2\lt\cdots \lt a_k\lt b_k$。
然后对每对位置 $(i,j)$，令 $A_i\gets A_i+1,B_j\gets B_j+1$。问使得 $A_i=B_i(l\le i\le r)$ 的最小操作数。
题解
令 $C_i=B_i-A_i$，于是上述操作的每对位置 $(i,j)$ 影响为 $C_i\gets C_i-1,C_j\gets C_j+1$，最终需要使得 $C_i=0$。
不难发现 $\sum_{i=l}^r C_i\neq 0$ 时必然无解，因为每次操作不改变 $C_i$ 之和。
另外 $C_i=0$ 等价于前缀和等于 $0$，然后上述操作的每次位置 $(i,j)$ 对前缀和的影响为 $i\sim j-1$ 的前缀和减一，其余不变。
于是 $C[l,r]$ 的最小前缀和小于 $0$ 时也必然无解。然后每次操作可以等效为选择 $[l,r-1]$ 的若干段前缀和减一，于是最小操作等于最大前缀和。
考虑线段树维护，时间复杂度 $O((n+q)\log n)$。
F. Sports Betting
题意
给定 $n$ 个队伍的能力值，队伍间两两进行一场比赛，队伍 $i$ 战胜队伍 $j$ 的概率为 $\frac {a_i}{a_i+a_j}$。
定义间接战胜：如果队伍 $i$ 战胜队伍 $b_1$，$b_1$ 战胜 $b_2\cdots b_k$ 战胜 $j$，则称 $i$ 间接战胜 $j$。
称一个队伍为冠军队伍当且仅当该队直接战胜或间接战胜所有其他队伍。问冠军队伍的期望个数。
题解
如果队伍 $i$ 战胜队伍 $j$，则从点 $i$ 向点 $j$ 连一条边。
设 $U=\{1,2\cdots n\}$，不难发现，假设冠军队伍集合为 $S$ 当且仅当 $S$ 为强连通分量且 $S$ 与 $U-S$ 的所有边方向为 $S\to U-S$。
设 $G(S,T)$ 表示 $S$ 与 $T$ 的所有边方向为 $S\to T$ 的概率，$f(S)$ 为 $S$ 构成强连通分量的概率，根据容斥定理，有
$$ f(S)=1-\prod_{T\subset S,T\neq \emptyset}G(T,S-T)f(T) $$
最终答案为
$$ \sum_{S\subseteq U}G(S,U-S)f(S)|S| $$
考虑如何计算 $G(S,T)$，有
$$ G(S,T)=\prod_{i\in S}\prod_{j\in T}\frac{a_i}{a_i+a_j} $$
显然可以暴力 $O(n^2)$ 计算单个 $G(S,T)$。预处理 $F(i,T)=\prod_{j\in T}\frac{a_i}{a_i+a_j}$，则 $G(S,T)=\prod_{i\in S}F(i,T)$ 可以 $O(n)$ 计算。
进一步，考虑将前 $\frac n2$ 个点染黑，其余点染白，记黑点集为 $U_1$，白点集为 $U_2$，于是有
$$ G(S,T)=G(S\cap U_1,T\cap U_1)G(S\cap U_1,T\cap U_2)G(S\cap U_2,T\cap U_1)G(S\cap U_2,T\cap U_2) $$
考虑 $O(n2^n)$ 预处理出下述四种情况
$$ G_{0/1,0/1}(S,T)=G(S,T)(S\subseteq U_1/S\subseteq U_2,T\subseteq U_1/T\subseteq U_2) $$
于是可以 $O(1)$ 计算 $G(S,T)$，总时间复杂度为 $O\left(3^n\right)$。
