给定长为 $n$ 的序列 $a$。要求支持以下操作：
$n,m\leq 2\times 10^5$。
又来了，要不然差临门一脚要不然是编译器出锅悬置指针导致了看似非常不合理的 undefined behavior。这已经不是简单的 frustration 了，要是考场上遇到这种根本没办法查出来的语言相关问题，不就三年 OI 一场空了么？
不过，正是因为考试前从没“用过”悬置指针，才会诱发这样的问题。这再次提醒我们，考场上千万不要使用不熟悉的语法糖，使用平时经大量验证的写法，纵使排版稍欠美观、或代码量增长少许，也是稳定而完备的。
不得不说，这几场“主题模拟赛”的题面中，唯这一场是最上心的。既将足球相关术语用平易近人的方式融合进题面里，又不使其过分冗长而消磨选手耐心。 （更多…）
本文记号可能稍显凌乱，但都能在题面或者前文中找到定义。
考虑枚举所有 $\newcommand\bigO{\operatorname{O}}\bigO(n^2)$ 个区间，预先计算它们本身的答案。记
$$\begin{aligned}g_a(l,r)&=\begin{cases}\max\{a_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\\g_b(l,r)&=\begin{cases}\max\{b_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\end{aligned}$$
则做前缀和 $s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i)$，对于询问 $[\text{ql},\text{qr}]$ 只需回答 $\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr})$ 即可。
令 $n, Q$ 同阶，时空复杂度 $\bigO(n^2)$。 （更多…）
一场相当有收获的比赛。比赛链接
尝试观察规律。我们发现，在完成$s$次操作以后，左端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s]$，右端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)$。假如现在我们达到最终状态，其$l=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}$。那么，在$x$的二进制表示中，如果从高到底第$\mathrm{pos}$位为$1$，则在第$\mathrm{pos}$轮中，有check (mid) == 0，向右区间递归；否则向左区间递归。这是很容易解释的：若向右递归，则右端点不变。而在下一层，右端点表示中$a, b$的所有系数乘$2$，所以体现为二进制位末尾添一个$0$。反之，就变成$(x+(x+1))/2$，在下一层中体现为$2x+1$。如果其有$\operatorname{popc}(x)$位为$1$，则到达该状态的概率为$p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}$。
以$s=3$时的状态$l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}$为例。$2$的三位二进制表示为$\text{0b010}$，则推断出在前三轮分别向右、左、右区间递归，到达其的概率为$p_0p_1^2$。 （更多…）