给定长为 $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)$。 （更多…）
仍然是中规中矩的一场模拟赛。前两题正解，第三题暴力，第四题不会。
考虑是否有两条及以上双向连边，若是则无解，若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。
这类数轴上带标号小球相撞的题目都有一个经典套路：两球相撞调转方向时，我们不认为是球本身转向，而认为两球仍然保持原方向运动，而其编号交换。 （更多…）
$4$ 道题全部只会暴力。还不如直接发下来当练习做呢，省得在场上罚坐三小时浪费时间。
观察发现：
设 $f(d,i,c_1,c_2)$ 表示“现在位于第 $d$ 层（此处“层”指的是节点实际深度）。已经填写好了 $a_1,a_2,\cdots,a_i$，且第 $d$ 层共 $c_1$ 个空置（非叶子）节点，第 $d-1$ 层有 $c_2$ 个此类节点”。那么两层的每一空置节点，均会有一个第 $d+1$ 层的儿子。枚举“下一层要填写 $k$ 个元素”，有转移
$$f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1)$$ （更多…）
Atcoder ARC149D – Simultaneous Sugoroku
官方题解做法是线性的，在此不再赘述。
考虑对于纸片 $X=1,2,\cdots,\max\{X_i\}$ 分别计算答案。每次暴力枚举显然不可取，但假若我们知晓对于 $X$，在 $i=0,1,\cdots,M$ 次操作以后纸片在数轴上的坐标 $x_0=X,x_1,\cdots,x_m$，其中 $\text{pos}$ 是最小的取到 $x_\text{pos}=-1$ 的位置，则对于 ${x_0}’=X’=X+1$：
这是可以用区间树维护的：我们想要快速求出全局非正数最大值以及首次取到该最大值的位置，同时支持全局加 $1$、后缀所有数符号翻转 （$\times -1$）。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置，采用延迟标记更新（两种操作对于前述信息是具有结合律的，形成幺半群）即可。
时间复杂度 $\operatorname{O}(\max\{X_i\}\log M)$，常数一般。
CodeForces Round #502 Problem G – The Tree
这是lty数据结构专题里唯二自己做出来的题目中的一道。
如果不包含“将 $x$ 的子树全部染白”的操作，应当怎样处理？
题目所给操作可以这样转述：令 $x$ 为本次染色操作的节点。若 $x$ 为白色，则立刻染黑并退出；否则我们找到其子树中的，与 $x$ 相连的黑色连通块，则对于每个连通块底部节点，若其不是叶子节点，我们将其儿子染黑。
由于本题的树没有特殊性质，且将来加入回退操作，故而难以维护整个连通块以及其叶子节点。因此，我们可以从“在何种情况下，节点 $x$ 被染黑”的方向考虑。
显然，只有从在 $x$ 到根的路径上的节点开始的染色操作，才可能波及到 $x$。假如最终 $x$ 被染黑的一瞬，它被包含在了以 $\text{comprt}$ 为根的连通块中。令链 $\langle\text{comprt}, x\rangle$ 为 $\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x$，那么自然想到，一种一定合法的染色序列是 $\{y_1,y_2,\cdots,y_n\}$，其中有 $\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\}$，也即我们每一步都在该连通块内部，并将连通块的最大深度推进一层。
这种序列确实合法（它是充分条件），但这真的是 $x$ 被染黑的必要条件么？ （更多…）
一道让我做得相当高兴的题目。
原题链接 （这是付费比赛。）
给定长度为 $n$ 的序列 $a$。定义函数 $f(S)=\sum\limits_{T\subseteq S} F^2(\sum_{s\in T} s)$，也即“对于 $S$ 的所有子集，求 $F(\text{子集所有元素之和})\text{的平方}$ 之和”。其中 $F(x)$ 为斐波那契数列的第 $x$ 项。有$F(0)=0, F(1)=1, F(x)=F(x-1)+F(x-2) (x > 1)$。
你需要支持以下操作，操作总数为 $m$：
1 x y：将 $a_x$ 修改为 $y$；
2 l r：输出 $\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}f(\{a_i, a_{i+1}, \cdots, a_{j}\})$，对 $998244353$ 取模。
数据范围：对于 $\text{50\%}$ 的数据，有 $n,m\leq 100$；对于 $\text{70\%}$ 的数据，有 $n,m\leq 1000$；对于 $\text{100\%}$ 的数据，有 $n,m\leq 10^5, a_i \leq 10^5$。
一场相当有收获的比赛。比赛链接
尝试观察规律。我们发现，在完成$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$。 （更多…）