比赛链接
M. V-Diagram
题意：给一个 \(V\) 图,求一个连续子序列平均值最大的 \(V\) 图。
设顶点是 \(x\)，答案一定是 \([1,x+1],[x-1,n],[1,n]\) 三者之一，复杂度 \(\Theta(n)\)。
J. Mysterious Tree
题意：一棵树，可能是链或者菊花，每次询问一条边存在性，确定是链还是菊花。询问次数 \(\lceil \dfrac{n}{2}\rceil + 3\)。
先依次询问 \((1,2),(3,4),\cdots\)，如果原树是菊花，那必定有且仅有一次询问是存在的，设为 \((u,u+1)\)，那中心点只可能是 \(u\) 或 \(u+1\)，随便选其他两个点 \((a,b)\) 询问，先问 \((u,a),(v,a)\)，拿有边的那个再询问 \(b\) 即可。
G. Snake
题意：给定 \(n \times m\) 地图上的一条长度为 \(k\) 的贪吃蛇。每次操作可以控制贪吃蛇移动一步或者缩短一格蛇身。对于每个位置，求从初始状态出发最少需要多少次操作使得蛇头到达该处。
对于所有初始被贪吃蛇覆盖的位置，设它为从头到尾第 \(p\) 个位置 \((x_p,y_p)\)，那么设 \(c_{x_p,y_p} = k-p+1\)，表示头到达这个位置时至少要 \(c_{x_p,y_p}\) 时刻之后，然后可以直接跑一个最短路 \(dis_{x',y'} = \max(dis_{x,y}+1,c_{x',y'})\)，复杂度 \(\Theta(nm\log{nm})\)。
对于取 \(\max\) 操作，可以拿另一个队列升序维护所有 \(dis_{x,y} = c_{x,y}\) 的位置，每次 bfs 时找到两个队列的头部最小值就行，复杂度 \(\Theta(nm+k\log k)\)。
H. Sweet Sugar II
\(n\) 个数 \(a_1,a_2,\cdots a_n\)，有 \(n\) 个事件，每个事件形如：如果 \(a_i < a_{b_i}\)，则 \(a_i \leftarrow a_i + w_i\)。事件随机顺序发生，问每个数的期望。
-
对于 \(a_i < a_{b_i}\) 的 \(i\)，由于 \(\forall i,w_i > 0\)，最后 \(a_i\) 一定是 \(a_i + w_i\)。设这种点是 \(A\) 类点。
-
对于 \(a_i \ge a_{b_i} + w_{b_i}\) 的 \(i\)，最后显然一定是 \(a_i\)。设这种是 \(B\) 类点。
-
对于 \(a_i < a_{b_i} + w_{b_i}\) 的 \(i\)，设这种为 \(C\) 类点。
首先 \(i \to b_i\) 一定是个基环树，对于 \(C\) 类点，肯定是经过若干个 \(C\) 类点，结尾是一个 \(A\) 类点，设 \(i = p_1,p_2\cdots p_k\)，其中 \(p_k\) 为 \(A\) 类点，那么如果最后变成 \(a_i + w_i\)，发生顺序一定是 \(p_k,\cdots p_1\)，概率显然是 \(\dfrac{1}{k!}\)。对于每个 \(C\) 类点算后面第一个 \(A\) 类点距离即可，可以记忆化搜索，复杂度 \(\Theta(n)\)。
E. Period of String
题意：给 \(n\) 个串，重排列每个串使得 \(s_i\) 是 \(s_{i+1}\) 的 period。其中 \(a\) 是 \(b\) 的 period 定义为 \(b_i = a_i \text{ mod } |a|\).
考虑直接模拟这个过程，先看 \(s_2\)，一定可以分解成若干 \(s_1\) 加上 \(s_1\) 的一个前缀，然后 \(s_3\) 一定可以分解成若干个 \(s_2\) 加上 \(s_2\) 的一个前缀，\(s_2\) 的一个前缀一定可以分解成若干 \(s_1\) 和 \(s_1\) 的一个前缀。
考虑分解串的这个过程，是找到 \(s_{i-1}\)，然后剩下的若干个 \(l<|s_{i-1}|\) 的位置再在 \(s_{i-1}\) 中找到前面的第一个长度 \(\le l\) 的整串。那么可以设 \(lst_{i,j}\) 为串 \(i\) 第 \(j\) 个位置可以匹配到的前面最长整串，若 \(|s_{i-1}| | j\)，那么 \(lst_{i,j} = i - 1\)，否则 \(lst_{i,j} = lst_{i-1,j \text{ mod } |s_{i-1}|}\)，然后设 \(fa_{i,j}\) 为串 \(i\) 的第 \(j\) 个位置最后分解出来对于 \(s_1\) 的哪个位置，有 \(fa_{i,j} = fa_{i-1,(j-1) \text{ mod } |s_{i-1}| + 1}\)。
判定串 \(s_i\) 时，设 \(pos\) 为当前合法的位置，初始为 \(1\)，那么每次找到 \(j\ge pos\) 的最大 \(lst_{i,j}\)，把 \([pos,pos+|s_{lst_{i,j}}| - 1]\) 匹配到 \(s_{lst_{i,j}}\)，可以直接统计字符出现次数来判定（可以写个链表防止复杂度劣化），然后最后无法匹配时剩下的长度就是 \(s_1\) 的一个前缀长度 \(len_i\)，并且此时还剩下 \(T_i\) 这些字符，设为 \((len_i,T_i)\)。
最后把 \((len_i,T_i)\) 按 \(len_i\) 排序，要求任意的 \((T_i \in T_{i+1})\) 即可。构造是简单的。
复杂度 \(\Theta(n\log n + \sum |s_i|)\)。
K. Card Game
题意：给一个牌序列，每次询问区间进行接龙游戏的剩余牌数。
设 \(dp_{l,r}\) 为 \([l,r]\) 游戏的答案，设 \(nxt_i\) 为 \(i\) 后面第一个 \(=a_i\) 的位置。
那么转移有 \(dp_{l,r} = dp_{l+1,r}+1(r < nxt_i)\)，\(dp_{l,r} = dp_{nxt_{i} + 1, r} (r \ge nxt_i)\)。
考虑优化转移，用一个主席树，每次先继承 \(l+1\) 的 dp 值，然后把 \([l,nxt_l - 1]\) 区间加 \(1\)，然后把 \([nxt_l + 1, n]\) 这些位置继承 \(nxt_l + 1\) 的子树即可。写一个永久化标记，注意继承 \(nxt_l + 1\) 的子树时要减去当前到根的标记，加上 \(nxt_l + 1\) 到根的标记。
复杂度 \(\Theta(n\log n)\)。
