2024/06/13(#50)：再见 和你说声再见

——《去明天》

72 [Ynoi Easy Round 2022] 堕天作战 TEST_98

倍增值域分块板子，但是为啥调了半天？？？

73 CF1270H Number of Components

首先没连通块仅当 $\max_{k=1}^{i} a_k>\min_{k=i+1}^n a_k$，因此我们只需要统计有多少个 $x$ 在 $a$ 序列中出现过，并满足将 $>x$ 的设置为 $1$，$\le x$ 的设置为 $0$ 之后序列中的 $10$ 段只有一个。

将 $10$ 段的个数记为 $f_x$，维护 $f$ 的线段树。然后每次会对 $[\min(a_i,a_{i+1}),\max(a_i,a_{i+1}))$ 的部分产生贡献。

74 CF1830D MEX Tree

直接树上背包即可。

75 THUPC2024 转化

考虑全搞到一个图里，如果内部能无限转那么就能搞出无限个，按照拓扑序随便算一下就行。

76 CTS2019 随机立方体

首先把恰好二项式反演掉。然后我们需要计算至少 $i$ 个极大点出现的概率。

钦定 $i$ 个极大点的方案数是 $\displaystyle A_{n}^{i} A_{m}^i A_l^i\times \prod_{j=1}^i \cfrac{1}{nml-(n-j)(m-j)(l-j)}$。后面这个东西可以理解为钦定每个点比它要比的东西都大的概率，因为前面强制钦定了 $i$ 个关键点的顺序。