Educational Codeforces Round 70$\text{(1202)}$
| $\text{Penalty}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ |
|---|---|---|---|---|---|---|
| $251$ | $\texttt{+}$ | $\texttt{+5}$ | $\texttt{-2}$ | |||
| $\text{00:12}$ | $\text{01:04}$ | |||||
| 补题 | √ | √ | √ | √ |
比赛时间：$\text{2022/7/21 14:30}$
A. You Are Given Two Binary Strings…
$\text{Solution:}$
因为是倒序字典序最小，所以我们要尽可能消除靠后的 $1$。
观察到 $k$ 会让 $\text{B}$ 串向左移 $k$ 位，我们判断一下 $\text{B}$ 串的最后一个 $1$，向左移到 $\text{A}$ 串第一个能移到的 $1$ 的位置。
B. You Are Given a Decimal String…
$\text{Solution:}$
首先不妨设 $dp_{x,y,i,j}$ 表示用 $x$ 和 $y$，从 $i$ 加到 $j$ 的最小步数。其中 $i,j$ 枚举 $0\sim100$。
$v_{x,y,i,j}$ 表示用 $x,y$，从末位为 $i$ 加到末位为 $j$ 的最小步数，这个可以通过 $dp$ 转移。
最终答案为：$\sum\limits_{i=1}^{|s|-1}v_{x,y,s_i,s_{i+1}}$。
时间复杂度 $\mathcal{O}(10\times10\times100\times100+10\times10\times |s|)$。
C. You Are Given a WASD-string…
$\text{Solution:}$
我们不妨假定初始位置为 $(0,0)$，在全程走到的极值坐标 $mix,mxx,miy,mxy$，那么面积为 $(mxx-mix+1)*(mxy-miy+1)$。
因为我们只能添加最多一步，所以答案只有可能变为 $(mxx-mix)*(mxy-miy+1)$ 或 $(mxx-mix+1)*(mxy-miy)$，我们只需判断能否在 $mix/miy$ 加 $1$ 的同时 $mxx/mxy$ 不变或 $mxx/mxy$ 减 $1$ 的同时 $mix/miy$ 不变，考场时忘记同时判断另一边不变。
D. Print a 1337-string…
$\text{Solution:}$
考虑构造序列为 $133\underbrace{77\cdots7} _ {cnt_7}\underbrace{33\cdot3}_{cnt_3}7 $。
得到的子序列数量为 $cnt_7+1+\dfrac{(cnt_3+2)(cnt_3+1)-1}{2}$，枚举 $cnt_3$，看 $cnt_7$ 能否满足长度在 $10^5$ 即可。
E. You Are Given Some Strings…
$\text{Solution:}$
我们不妨从文本串找到一个划分点 $i$，分成 $[1,i]$ 和 $[i+1,n]$ 两段，我们可以找所有模式串匹配前半部分的后缀的数量，所有模式串匹配后半部分前缀的数量，将两部分相乘就能得到第 $i$ 位的贡献。由于后半部分等价于前半部分翻转，所以考虑前半部分。
将文本串存入 trie 树，求出 fail 指针，因为失配的定义就是跳到下一个与当前串有最大公共后缀的串的编号，如果 $p$ 能匹配，那么 $fail_p$ 也可以匹配，所以 $p\rightarrow fail_p$ 作为更新，最后遍历文本串，若此时遍历到了第 $i$ 位，匹配到了 $p$ 节点，则有 $f_i=ed_p$。
然后将两边都算出来就解决了这道题。
时间复杂度 $\mathcal{O}(|T|+\sum|S|)$。
$\text{Code: }$Submission #165291628 - Codeforces
F. You Are Given Some Letters…
$\text{Solution: }$
不妨考虑枚举完整的循环节数 $p$,此时对应的 $k$ 的范围为 $[l,\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}]$。
设一个循环节 $\texttt{a}$ 的数量为 $a’$，$\texttt{b}$ 的数量为 $b’$，则有：
$\lfloor\dfrac{a}{p+1}\rfloor\le a’\le \lfloor\dfrac{a}{p}\rfloor - ①$
$\lfloor\dfrac{b}{p+1}\rfloor\le b’\le \lfloor\dfrac{b}{p}\rfloor - ②$
$①+②$ 得：$\lfloor\dfrac{a+b}{p+1}\rfloor\le a’+b’\le\lfloor\dfrac{a+b}{p}\rfloor$
而 $k=a’+b’$，两个范围取交则得到了循环节数量为 $p$ 时 $k$ 的取值方案，计算过后，将 $l$ 设为 $\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}+1$。
时间复杂度 $\mathcal{O}(\sqrt{a+b})$。
Educational Codeforces Round 71$\text{(1207)}$
比赛时间：$\text{2022/1/29 20:05}$
| $\text{Penalty}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ | $\texttt{G}$ |
|---|---|---|---|---|---|---|---|
| $251$ | $\texttt{+}$ | $\texttt{+1}$ | $\texttt{+1}$ | $\texttt{+}$ | $\texttt{+}$ | $\texttt{+1}$ | |
| $\text{00:03}$ | $\text{00:12}$ | $\text{00:25}$ | $\text{00:44}$ | $\text{01:01}$ | $\text{01:16}$ | ||
| 补题 | √ |
A. There Are Two Types Of Burgers
$\text{Solution:}$
看哪个贵就先做哪个，若还有剩余的面包就再做另一个。
B. Square Filling
$\text{Solution:}$
操作次数可以达到 $n^2$，故判断一下每一个小正方形是否能进行操作，最后检查操作后的矩阵是否为所求矩阵。
$\text{Extention:}$
找到一种操作次数最少的方案。
C. Gas Pipeline
$\text{Solution:}$
定义 $dp_{i,1/2}$ 表示当前进行到第 $i$ 个位置，且当前的高度为 $1/2$ 的最小费用。
考虑通车和不通车的情况：
- 通车：$dp_{i,2} = dp_{i-1,2}+a+2b$；
- 不通车：$dp_{i,1}=\min(dp_{i-1,1}+a+b,dp_{i-1,2}+2a+b)$,$dp_{i,2}=\min(dp_{i-1,2}+a+2b,dp_{i-1,1}+2a+2b)$。
注意第一个和最后一个的高度已被确定为 $1$，所以 $dp_{0,1}=b,dp_{0,2}=Inf$，最后答案为 $dp_{n,1}$。
D. Number Of Permutations
$\text{Solution:}$
利用容斥原理，将答案转化为求总方案数减 $a$ 排好序的方案数减 $b$ 排好序的方案数加 $a,b$ 都排好序的方案数。
注意 $a,b$ 可能无法同时都排好序。
E. XOR Guessing
$\text{Solution:}$
观察到这个数在二进制下不超过 $14$ 位，且每次询问 $100$ 个数。
故第一次询问，用 $100$ 个前 $7$ 位全部为 $1$ 的数，这样这个数前 $7$ 位就可以确定。
第二次询问，用 $100$ 个后 $7$ 位全部为 $1$ 的数，这样这个数的后 $7$ 为也可以确定。
最终将两次结果拼起来即可，因为 $2^7=128>100$，故一定能找到 $100$ 个前 $7$ 位相同或 $100$ 个后 $7$ 位相同的数。
F. Remainder Problem
$\text{Solution:}$
本题采用根号分治。
我们需要额外开一个数组 $sum_{i,j}$ 表示所有下标模 $i$ 余 $j$ 的数之和，但我们只需保存 $1\le i\le \sqrt{n},0\le j<i$ 的情况。
- 进行修改操作时，枚举 $1\le i \le \sqrt{n}$ 更新 $sum_{i,x\mod i}$，复杂度 $\mathcal{O}(\sqrt{n})$；
- 进行查询操作，若 $1\le x\le \sqrt{n}$，直接查 $sum$ 即可，复杂度 $\mathcal{O}(1)$，若 $x>\sqrt{n}$，暴力查询即可，复杂度 $\mathcal{O}(\sqrt{n})$。
总时间复杂度 $\mathcal{O}(n\sqrt{n})$，空间复杂度 $\mathcal{O}(n)$。
终于知道时限为什么给 $4$ 秒了。
*G. Indie Album
$\text{Solution:}$
一道 AC 自动机的深层运用。
首先对于一棵字典树，求出每个节点 $i$ 的 $fail_i$，并连一条 $fail_i \rightarrow i$ 的有向边，称新建出的树为 $fail$ 树。
则有，字符串 $x$ 在字符串 $y$ 中出现的次数为， $fail$ 树中 $x$ 的结束节点为根的子树中 $y$ 字符串的节点的数目。
将询问离线，在 $i$ 字符串结尾节点打入新字符串的结尾节点，然后搜索 $Trie$ 树，每到一个节点，节点权值 $+1$，碰到查询时需要查询子树和。
时间复杂度 $\mathcal{O}(|T|\log|T|)$。
$\text{Code: }$Submission #145308976 - Codeforces
Educational Codeforces Round 122$\text{(1633)}$
| $\text{Penalty}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ |
|---|---|---|---|---|---|---|
| $55$ | $\texttt{+}$ | $\texttt{+}$ | $\texttt{+}$ | $\texttt{+}$ | ||
| $\text{00:02}$ | $\text{00:06}$ | $\text{00:17}$ | $\text{00:30}$ | |||
| 补题 | √ | √ |
比赛时间： $\text{2022/1/31 22:35}$
A. Div. 7
$\text{Solution:}$
对于一个数 $x$，如果它能被 $7$ 整除，则不作修改直接输出，否则调整它的个位，找到一个能被 $7$ 整除的数输出。
因为每连续 $7$ 个数就会有一个被 $7$ 整除，所以一定会有一个数符合要求。
B. Minority
$\text{Solution:}$
不难想到将整个字符串全部选中的贡献。
若 $\texttt{0}$ 和 $\texttt{1}$ 的数量相等，我们只要去掉开头或结尾就取得最优答案；
若 $\texttt{0}$ 和 $\texttt{1}$ 的数量不等，我们全选就可以做到最优答案。
可以证明其它的选择一定不优于这么选择。
C. Kill the Monster
$\text{Solution:}$
硬币的数量很少，考虑枚举用来加血的硬币的数量，然后只需判断谁能赢即可。
时间复杂度 $\mathcal{O}(\sum k)$。
$\text{Extention:}$
$\sum k \le 10^9$
D. Make Them Equal
$\text{Solution:}$
一个最直接的想法：对于一个值 $x$，求出从 $1$ 操作到 $x$ 的最小次数 $v_x$，然后问题就变成了你有容量为 $k$ 的背包，和 $n$ 个体积 $v_i$，价值 $c_i$ 的物品，求最大的价值。
这不就是一个0-1背包的事。
但看了看范围 $n\le10^3,k\le10^6$，0-1背包复杂度是 $\mathcal{O}(nk)$，不可过啊。
但当你求出 $v$ 后发现：最大的 $v_x$ 竟然不超过 $12$，也就是操作数最多不会超过 $12n$。
那么我们可以先求一个 $sumv$，然后与 $k$ 取 $\min$，复杂度就降到了 $\mathcal{O}(12n^2)$。
$\text{Code: }$Submission #144900381 - Codeforces
E. Spanning Tree Queries
$\text{Solution:}$
暴力做法是：对于一个询问，把边权都跑出来，然后做一次最小生成树，时间复杂度 $\mathcal{O}(qm\log m)$。
但细想之后，发现我们并不用对于每一次询问都跑一次最小生成树，如果边的大小关系没有因为这次询问而变化，那么选出的最小生成树边集还会由上一次的边集组成。
那么我们如何得知边的大小关系发生了改变呢？
比如，对于两条边 $x$ 和 $y$，它们的边权为 $w_x$ 和 $w_y$ 且 $w_x<w_y$，设当前询问的值为 $v$。
- 当 $v< w_x$ 时，$w_x-v<w_y-v$；
- 当 $w_x\le v< \lfloor \dfrac{w_x+w_y}{2} \rfloor+1$ 时，$v-w_x \le w_y-v$；
- 当 $\lfloor \dfrac{w_x+w_y}{2}\rfloor +1\le v< w_y$ 时，$v-w_x>w_y-v$；
- 当 $v\ge w_y$ 时， $v-w_x<v-w_y$。
所以可得，对于每两条边，共有 $4$ 种情况，所以总共的情况也只有 $m^2$ 量级，可以接受。
那么我们只需将原边权与 $\lfloor \dfrac{w_x+w_y}{2}\rfloor+1$ 放入一个数组并排序，再将所有询问排序。
当询问的值又超过了一条新边的边权，代表有边的大小关系改变，我们需要重求一遍最小生成树；若这一次询问的并没有使边的大小关系发生改变，我们仍然可以用上一次最小生成树的结果，再加上这次询问对绝对值的贡献。
时间复杂度 $\mathcal{O}(q\log q+m^3\log m)$。
但如果把优先预处理出所有最小生成树的情况，询问的时候二分出对应的情况，复杂度会变为 $\mathcal{O}(q\log m^2+m^3\log m)$，稍有优化。
$\text{Code: }$Submission #144900383 - Codeforces
*F. Perfect Matching
$\text{Solution:}$
依题意，分析满足完美匹配的条件。
我们有一种贪心的策略来检查是否可以完美匹配：定义一次匹配操作为选择当前最深的激活节点，与它的父亲之间连边，并删去这两个点，重复一次匹配操作，直到激活节点全部被清空即为完美匹配。时间复杂度 $\mathcal{O}(n)$。
观察到 $1$ 操作次数很多，而真正要求输出方案的 $2$ 操作数目很少，考虑能否快速有效地判断当前情形是否能完美匹配。
因为每次激活的节点必须与之前激活的节点连通，那么每次激活都会仅有一个包含全部激活节点的连通块，且连通块也是树，暂时称为激活树，考虑激活树有什么条件才能满足完美匹配。
我们先令一个节点，它的子树（包括自己）的总共的激活节点的数目为奇数，称之为奇数节点，反之称为偶数节点。
如果这棵激活树能够完美匹配，对于每一次匹配操作，取出的子节点和父节点当且仅当子节点是父节点唯一的儿子。
若此子节点不是父节点唯一的儿子，由匹配操作定义，树的结构如图所示：
删除 $u$ 和 $v_1$ 后，$v_2$ 与 $v_3$ 必然无法形成完美匹配，与假设矛盾。
那么每一次匹配，一定是一个奇数节点和一个偶数节点，且在删除后，其它节点的子树（包括自己）的总共的激活结点数目要么减 $2$，要么无变化。则其余的奇偶节点仍无变化。
故可推出一个重要结论：若激活树能完美匹配当且仅当奇数节点数目等于偶数节点数目。
那么现在问题就转化为了：
- 添加一个点，翻转它的父亲到 $1$ 节点这条路径上所有节点的状态；
- 查询一个点到 $1$ 节点这条路径上奇数节点的数目。
用树剖解决即可。
在进行 $2$ 操作时，只需 $dfs$ 一遍，求子树 $sz$，判断这个点是否为奇数节点，如果是就将此节点和其父亲连接。
时间复杂度 $\mathcal{O}(n\log^2 n)$。
$\text{Code: }$Submission #144900385 - Codeforces
CodeTON Round 1$\text{(1656)}$
比赛时间： $\text{2022/7/28 08:30}$
| $\text{Score}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ | $\texttt{G}$ | $\texttt{H}$ | $\texttt{I}$ |
|---|---|---|---|---|---|---|---|---|---|
| $6098$ | $\texttt{496}$ | $\texttt{976}$ | $\texttt{1404}$ | $\texttt{1696}$ | $\texttt{1530}$ | ||||
| $\text{00:04}$ | $\text{00:10}$ | $\text{00:16}$ | $\text{00:38}$ | $\text{01:37}$ | |||||
| 补题 | √ | . |
为即将到来的 CodeTON Round 2 练习一下。
A. Good Pairs
$\text{Solution:}$
考虑 $|a_i-a_k|+|a_k-a_j|=|a_i-a_j|$ 什么时候成立，即找到 $a_i\le a_k\le a_j$ 的三元组，由于题目保证有解，所以取最小值和最大值就行。
B. Subtract Operation
$\text{Solution:}$
考虑 $n$ 个数为 $a_1,a_2\cdots,a_n$。第一次我们消去 $a_p$，则序列变为 $a_1-a_p,a_2-a_p,\cdots,a_n-a_p$。
再次消掉 $a_q$，则原序列变为 $(a_1-a_p)-(a_q-a_p),(a_2-a_p)-(a_q-a_p),\cdots,(a_n-a_p)-(a_q-a_p)$ 也就是 $a_1-a_q,a_2-a_q,\cdots,a_n-a_q$，这样我们可以发现，在第 $1\sim (n-2)$ 次选择的数全部被抵消，最后剩下一个 $a_x-a_y$ 的形式，直接用 map 维护一下有没有相差为 $k$ 的数。
C. Make Equal With Mod
$\text{Solution:}$
如果序列中没有 $1$，从最大数开始，一个一个模成 $0$，没有任何问题。
如果序列中存在 $1$，那么就需要将所有数都变成 $1$，对于最大数，我们要模最大数减 $1$，所以我们要判断是否有大小相差为 $1$ 的数，如果没有，即能满足要求。
D. K-good
$\text{Solution:}$
如果 $n$ 是 $k$-good 数，当且仅当：
$n=pk+\dfrac{k(k-1)}{2},p\in \mathbb{N}$
考虑进一步转化：
$\Rightarrow 2n=2pk+k(k-1)$
$\Rightarrow 2n=k(2p+k-1)$
考虑 $k$ 和 $2p+k-1$ 的奇偶性不同，则一定是 $2$ 的正整数次幂和一个奇数相乘的组合，又因为 $k<2p+k-1$，取 $k=\min(2^m,\dfrac{2n}{2^m})$，如果 $k=1$ 则输出 $-1$。
E. Equal Tree Sums
$\text{Solution:}$
记 $u$ 的子节点个数为 $k$，分别为 $v_1,v_2,\cdots,v_k$，$sum_u$ 表示以 $u$ 为根的子树权值和，以 $1$ 为根节点时，以 $u$ 为划分点，有如下的式子：
$sum_{v_1}=sum_{v_2}=\cdots=sum_{v_k}=sum_1-sum_u$
$sum_u=a_u+\sum\limits_{i=1}^{k}sum_{v_i}$
则 $a_u=sum_u-\sum\limits_{i=1}^ksum_{v_i}$
$=sum_u-k(sum_1-sum_u)$
$=(k+1)sum_u-ksum_1$
我们不妨假设树的总权值和为 $0$，那么就有：
$a_u=(k+1)sum_u$
$sum_{v_1}=sum_{v_2}=\cdots=sum_{v_k}=-sum_u$
这样 $sum_u=(k+1)sum_u-ksum_u=sum_u$，刚好满足。
具体实现的话，可以使 $sum_u=(-1)^{dep_u}$，$sum_1=0$，就能构造出合法权值。
F. Parametric MST
$\text{Solution:}$
不妨先将 $a$ 按升序排序，考虑设 $b_u(t)=a_u+t$。
那么 $w_{i,j}(t)=(a_i+t)(a_j+t)-t^2=b_i(t)b_j(t)-t^2$，也就是当 $i,t$ 一定时，$w_{i,j}(t)$ 有最小值：
- 当 $b_i(t)<0$ 时，取 $b(t)$ 的最大值，即 $j=n$；
- 当 $b_i(t)>0$ 时，取 $b(t)$ 的最小值，即 $j=1$。
那么我们对于一个 $t$，就有如下的连边方式：
- 如果 $b_i(t)<0,i\neq n$，$i$ 向 $n$ 连边。
- 如果 $b_i(t)>0,i\neq 1$，$i$ 向 $1$ 连边。
- 如果 $(1,n)$ 间重边，删去一条。
这样连边构成了一棵树，且是 $K_n(t)$ 的最小生成树。
我们不妨考虑当 $t$ 取 $(-\infty,-a_n)$ 与 $(-a_1,+\infty)$ 时的函数。
当 $t\in (-\infty,-a_n]$ 时，$b_1(t)\le b_2(t)\le \cdots\le b_n(t)< 0$，那么最小生成树为 $1\sim n-1$ 向 $n$ 连边。
$K_n(t)=a_n(sum-a_n)+t\cdot((n-1)a_n+(sum-a_1))$
$=((n-2)a_n+sum)t+a_n(sum-a_n)$
这是一个一次函数的形式，当斜率 $(n-2)a_n+sum<0$ 时， $\lim\limits_{t\to -\infty}K_n(t)=+\infty$，无最大值。
当 $t\in[-a_1,+\infty]$ 时，同理，得斜率 $(n-2)a_1+sum>0$ 时，无最大值。
接下来考虑 $[-a_n,-a_1]$ 的情况。
一个结论是 $t$ 需要取在 $-a_i$ 上，若在两个相反数之间，因为一段之间是一次函数，必定在端点上取最小值。
那么我们考虑 $t$ 从 $-a_1$ 开始 $-a_i\rightarrow -a_{i+1}$，函数的变化。
考虑 $K_n(-a_1)=((n-2)a_1+sum)(-a_1)+a_1(sum-a_1)$
由于整个函数是连续的，则 $K_n(-a_2)=((n-2)a_1+sum)(-a_2)+a_1(sum-a_1)$，即斜率暂时不变。
那么函数变化为：$-((n-2)a_1+sum)a_1\rightarrow-((n-2)a_1+sum)a_2$，即当前斜率 $k*(-a_2-(-a_1))$。
当转成新一部分的斜率时，斜率从 $((n-2)a_1+sum)$ 变为 $((n-2)a_1+(sum-a_1-a_2)+a_n-a_2)=((n-3)a_1+sum+a_n)$，改变为 $-a_1+a_n$。
这样我们就解决了这道题。
时间复杂度上界为排序的 $\mathcal{O}(n\log n)$。
$\text{Code: }$ Submission #165986233 - Codeforces
Codeforces Global Round 21$\text{(1696)}$
比赛时间：$\text{2022/7/30 08:30}$
| $\text{Score}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ | $\texttt{G}$ | $\texttt{H}$ |
|---|---|---|---|---|---|---|---|---|
| $4040$ | $\texttt{492}$ | $\texttt{964}$ | $\texttt{1216}$ | $\texttt{1368}$ | ||||
| $\text{00:04}$ | $\text{00:09}$ | $\text{00:39}$ | $\text{01:19}$ | |||||
| 补题 | √ | . |
A. NIT orz!
$\text{Solution:}$
因为 $z$ 只能被进行与操作，也就是 $z$ 在二进制下 $1$ 的个数越来越少，所以我们不如用最开始的 $z$ 去和 $a$ 中的数进行或操作求得最大值。
B. NIT Destroys the Universe
$\text{Solution:}$
首先，进行两次 $l=1,r=n$ 的操作就能使 $a_i=0$，所以答案上限是 $2$。
如果序列中只有 $1$ 段连续的不为 $0$ 的数，那么答案为 $1$，如果全 $0$ 答案是 $0$。
C. Fishingprince Plays With Array
$\text{Solution:}$
考虑两种操作是互逆的，也就是如果我们把某个数分开，可以随时合回来。
那么可以先将 $a$ 序列和 $b$ 序列能拆分的全部拆分，即 $qa_i$ 和 $ta_i$ 表示 $a_i$ 能拆成的最小数和拆出的个数，$qb_i$ 和 $tb_i$ 表示 $b_i$ 能拆成的最小数和拆出的个数。
考虑只有一段连续相同 $qa$ 和 $qb$ 才能合并，计算 $\sum ta$，判断 $qb$ 是否等于 $qa$ 且 $\sum tb$ 是否等于 $\sum ta$，不断用指针向前移动，最后两串全部匹配成功就输出 Yes。
D. Permutation Graph
$\text{Solution:}$
我们先得到整个数组 $a$ 的最大值编号为 $id$，不难发现 $[1,id-1]$ 无法向 $[id+1,n]$ 连边，那么我们就必须先想办法从 $[1,id-1]$ 跳到 $id$ 再去跳到 $[id+1,n]$。
接下来去考虑 $[1,id-1]$ 中的最小值为 $p$。首先 $[1,p-1]$ 肯定可以走到 $p$，而 $p$ 肯定能跳到 $id$，所以我们就不必去管 $[p+1,id-1]$，因为答案不优。这样我们就递归到了一个更小的区间。
$[id+1,n]$ 的考虑也是同理，找到最小值后，但这次我们只需求靠右的区间即可。
本题中需要注意两个点：
- 如果当前求的区间最大值，接下来递归时就有改求区间最小值，然后再次递归再求区间最大值，即每次最大最小转换。
- 如果当前求的最小值就在 $1$ 或 $n$，则可以省去这一步。
具体维护上，带一个 log 也可以，复杂度 $\mathcal{O}(n\log n)$。
E. Placing Jinas
$\text{Solution:}$
首先，不难发现，本题并不是最优解问题，因为移动的步数确定，我们只要考虑移动需要多少步。
我们考虑 $f(x,y)$ 为点 $(x,y)$ 的操作次数，那么答案为 $\sum\limits_{i=0}^n\sum\limits_{j=0}^{a_i}f(i,j)$。
不难发现 $f(x,0)=1,f(0,y)=1,f(x,y)=f(x-1,y)+f(x,y-1)$。即 $f(x,y)={x+y\choose x}$ 。（斜着的杨辉三角）
算到这是 $O(n^2)$ 的，但是推过结论的应该已经都会了，这里再来推一下：
考虑第 $i$ 行的贡献：
$\sum\limits_{j=0}^{a_i-1}f(i,j)=\sum\limits_{j=0}^{a_i-1}{i+j\choose i}=\sum\limits_{j=0}^{a_i-1}\dfrac{A_{i+j}^i}{A_i^i}=\dfrac{\sum\limits_{j=0}^{a_i-1} A_{i+j}^i}{A_i^i}$
而 $\sum\limits_{j=0}^{a_i-1} A_{i+j}^i$ 是整数裂项的形式，化简后为 $\dfrac{\prod\limits_{j=a_i-1}^{a_i+i}j}{i+1}=\dfrac{A_{a_i+i}^{a_i+i}}{(i+1)A_{a_i-1}^{a_i-1}}$
最终 $\sum\limits_{j=0}^{a_i}f(i,j)=\dfrac{A_{a_i+i}^{a_i+i}}{(i+1)A_{a_i-1}^{a_i-1}A_i^i}=\dfrac{A_{a_i+i}^{a_i+i}}{A_{a_i-1}^{a_i-1}A_{i+1}^{i+1}}={a_i+i\choose a_i-1}$。
于是预处理阶乘和逆元，复杂度为 $\mathcal{O}(n)$。
CodeTON Round 2$\text{(1704)}$
比赛时间：$\text{2022/7/31 22:05}$
| $\text{Score}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ | $\texttt{G}$ | $\texttt{H1}$ | $\texttt{H2}$ |
|---|---|---|---|---|---|---|---|---|---|
| $3406$ | $\texttt{489}$ | $\texttt{719}$ | $\texttt{1130}$ | $\texttt{1068}$ | |||||
| $\text{00:07}$ | $\text{00:13}$ | $\text{00:30}$ | $\text{01:44}$ | ||||||
| 补题 | √ | √ | . |
打的仍然没有达到我的预期。
$\texttt{AB}$ 做的较慢，但靠 $\texttt{C}$ 挽救了回来，而 $\texttt{D}$ 挂了两发还是很晚才过，况且写法复杂，结论靠猜，算是实力缺陷的体现。
不过说实话，以现在的水平，真的无法快速想到 $\texttt{D}$ 的性质，希望能有四十分钟开出前 $4$ 题的时候吧。
A. Two 0-1 Sequences
$\text{Solution:}$
每次操作只能改 $a$ 串的前两位，所以 $a$ 的后 $m-1$ 位不能动，这样只需匹配 $a$ 和 $b$ 的后 $m-1$ 位，再看 $a$ 的 $1\sim n-m+1$ 位有没有 $b_1$。
B. Luke is a Foodie
$\text{Solution:}$
考虑如果一段连续的区间的最大值和最小值相差超过 $2x$，那么一定需要更换。那么我们只需模拟一下，看看哪些地方需要更换即可。
C. Virus
$\text{Solution:}$
用最开始被感染的房屋将所有房子划分为若干个小段，我们可以用两天把一段区间的边界给保护，这样中间全都不用保护，现在考虑进行这个操作的顺序。
不难想到应该从大区间往小区间封闭，因为每天每段区间会有两个房子被感染，而如果一段区间被感染完就不会再被感染，所以先去保护大区间，小区间可能在中途被感染完，损耗的房屋更少。
D. Magical Array
$\text{Solution:}$
考场上想的做法是将 $c$ 数组用反操作处理，选择最靠两段的数，把它往中间移动，最后合并的不能合为止。然后发现有 $m-1$ 个序列是一样的，找到特殊序列后，通过观察样例发现 $2$ 操作次数，就是合并后特殊序列进行多少次单独的移动得到非特殊序列，然后就通过了，做法猜的东西很多。
题解是这样的：
设每一位的权值为 $a_i\times i$。则非特殊序列的其中四个位置 $(i,i+1,j-1,j)$ 的权值为 $a_i\times i+a_{i+1}\times(i+1)+a_{j-1}\times(j-1)+a_j\times j$，进行 $(i+1,j-1)$ 操作 $1$ 后，仍然考虑这 $4$ 个位置的权值和，其它位置的权值不变。
$(a_i+1)\times i+(a_{i+1}-1)\times(i+1)+(a_{j-1}-1)\times(j-1)+(a_j+1)\times j$
$=a_i\times i+a_{i+1}\times(i+1)+a_{j-1}\times(j-1)+a_j\times j+i-(i+1)-(j-1)+j$
$=a_i\times i+a_{i+1}\times(i+1)+a_{j-1}\times(j-1)+a_j\times j$
所以在操作后总权值不变，这样求出 $\sum a_i\times i$ 就能找出特殊数组。
考虑进行一次操作 $2$ 权值的变化情况，考虑 $(i,i+1,j-2,j)$。
$(a_i+1)\times i+(a_{i+1}-1)\times(i+1)+(a_{j-2}-1)\times(j-2)+(a_j+1)\times j$
$=a_i\times i+a_{i+1}\times(i+1)+a_{j-2}\times(j-2)+a_j\times j+i-(i+1)-(j-2)+j$
$=a_i\times i+a_{i+1}\times(i+1)+a_{j-2}\times(j-2)+a_j\times j+1$
每次 $2$ 操作后，数组的总权值和加 $1$，这样我们用非特殊序列的权值和减特殊序列的权值和，即能得到 $2$ 操作次数。
这个方法完美的避开了具体的构造方案，对序列定义一个权值，使操作有了固定的性质，成为了一个充要条件。
时间复杂度 $\mathcal{O}(n)$。
E. Count Seconds
$\text{Solution:}$
首先只有一个点没有出边，称其为汇点。
我们考虑先模拟前 $n$ 轮，目的是如果经过 $n$ 轮后，$a_u$ 仍然有值，那么 $u$ 到汇点整条上路径的点值都会大于 $0$，保证每个不为 $0$ 的位置能直接贡献到汇点。
然后还剩下的每一点权值都能多撑一个单位的时间，跑个拓扑排序计算总和即可，别忘了加上开始模拟的时间。
如果模拟不到 $n$ 轮就结束了，记得特判。
时间复杂度 $\mathcal{O}(n^2)$。
F. Colouring Game
$\text{Solution:}$
一次操作最少可改变自己的 $1$ 个字符，如果 $\texttt{R}$ 和 $\texttt{B}$ 的个数不同，那么一定个数多的赢。
当 $\texttt{R}$ 和 $\texttt{B}$ 的个数相同时，记一段 $\texttt{RBRB}\cdots$ 的长度为 $l$。那么每次每个人都会选择一段 $\texttt{RB}$ 或 $\texttt{BR}$ 消掉，两人可以同时操作且操作后局面相同，是公平博弈论，可以求 $SG$ 函数。
$SG_l=\text{mex}(SG_{i-1}\oplus SG_{l-i-1})$
求出 $SG$ 后发现，当 $l\ge 69$ 时，有长度为 $34$ 的循环节，所以只用打表前 $34\times3=102$ 位 $SG$ 就足够。
Codeforces Round #809 (Div. 2)$\text{(1706)}$
比赛时间：$\text{2022/7/18 22:35}$
| $\text{Score}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D1}$ | $\texttt{D2}$ | $\texttt{E}$ |
|---|---|---|---|---|---|---|
| $2214$ | $\texttt{494}$ | $\texttt{920}$ | $\texttt{800}$ | $\texttt{-1}$ | ||
| $\text{00:03}$ | $\text{00:20}$ | $\text{01:00}$ | ||||
| 补题 | √ | √ | √ |
这打的是什么垃圾，策略有误而且能力还有欠缺。
A. Another String Minimization Problem
$\text{Solution:}$
按题意模拟，注意要先改靠前的位置。
B. Making Towers
$\text{Solution:}$
考虑一个相同颜色的塔，由于必须得连着，只能先往右/左走几次，到下一行后再往左/有走几次，也就是说只有每两个之间相距偶数个才能放在同一列上。
随便写写就过了。
C. Qpwoeirut And The City
$\text{Solution:}$
这题开始以为需要 dp，但其实只需要模拟，因为偶数的情况看似复杂，实际上只有 $2$ 类：
- 全都在奇数或偶数格；
- 有一对相距两格且前者必须在奇数格上，而其余位置固定。
这样就很好写了，忘记前缀和优化还挂了一发，真是服了。
时间复杂度 $\mathcal{O}(n)$。
D. Chopping Carrots
$\text{Solution:}$
简单版做法很多，由于对于 $\lfloor \dfrac{a_i}{p_i}\rfloor$，不同的取值最多只有 $2\sqrt{a_i}$，直接将所有取值都记下来，按P7514 [省选联考 2021 A/B 卷] 卡牌游戏做即可。
复杂版无法支持我们存储所有取值，那么我们可以枚举 $\lfloor \dfrac{a_1}{p_1}\rfloor$ 的所有可能取值，记为 $b$，然后找到 $a_2\sim a_n$ 得到的小于等于 $b$ 的最大值和大于等于 $b$ 的最小值，再用双指针更新答案。时间复杂度 $\mathcal{O}(\sqrt{a_1}\times n\log n)$，自带大常数容易被卡常。
下面参考题解的 $\text{Solution 2}$，可以作为一个很好的 $\text{idea}$。
假定 $v$ 为 $\lfloor \dfrac{a_i}{p_i}\rfloor$ 的最大值，则我们只需最大化 $\lfloor \dfrac{a_i}{p_i}\rfloor$ 的最小值。
考虑如果 $1\le a_i\le v$，则我们希望将 $p_i$ 取为 $1$，取 $2$ 及以上答案不优。
如果 $v+1\le a_i\le 2v$，则我们希望将 $p_i$ 取为 $2$，以此类推。
如果 $(u-1)\cdot v+1\le a_i \le u\cdot v$，则我们希望将 $p_i$ 取为 $u$。
但是我们如何对于满足 $(u-1)\cdot v+1\le a_i \le u\cdot v$ 的所有的 $a_i$ 计算最小值？不难发现，这些数的 $p_i$ 均取 $u$，所以我们只需求出这部分数的最小值即可。
记 $next_i$ 为所有 $a_i$ 中大于等于 $i$ 的最小值，这可以通过预处理轻松求出，这样，我们对于 $u=1\sim k$，查询 $next_{(u-1)\cdot v+1}$ 就能得到。
两个重要的细节：
- 如果存在 $a_i\ge(v+1)\cdot k$，那么 $v$ 就不可能作为最大值，直接跳过。
- 对于某个 $v$，我们只需要检查满足 $(u-1)\cdot v+1\le a_n$ 的 $u$，更大的没有意义。
最后时间复杂度 $\mathcal{O}(\sum\limits_{i=1}^{a_n}\dfrac{a_n}{a_i})=\mathcal{O}(a_n \log a_n)$。
这个复杂度居然连根号都不带，不得不说非常优秀。
E. Qpwoeirut and Vertices
$\text{Solution:}$
考虑将第 $i$ 条给定的边给定一个边权 $i$，然后跑一个最小生成树。通过最小生成树的性质，任意两点之间都有唯一路径，且涵盖的边权最大值尽可能小，正好符合我们的要求。
我们通过倍增求最近公共祖先，就能有两点之间的路径上的边权最大值，考虑如何拓展到 $[l,r]$ 区间任意两点。
由于我们只需对所有被经过的边取最大值，我们可以只去求相邻两点的最近公共祖先，就能涵盖到所有要求的路径。（想一想应该也可以理解）
最后用倍增就能得到答案。
时间复杂度 $\mathcal{O}(n\log n)$。
Codeforces Round #808$\text{(1707)}$
比赛时间：$\text{2022/7/16 22:35}$
| $\text{Score}$ | $\texttt{2A}$ | $\texttt{2B}$ | $\texttt{2C/1A}$ | $\texttt{2D/1B}$ | $\texttt{2E/1C}$ | $\texttt{2F/1D}$ |
|---|---|---|---|---|---|---|
| $1452$ | $\texttt{492}$ | $\texttt{960}$ | $\texttt{-3}$ | |||
| $\text{00:04}$ | $\text{00:10}$ | |||||
| 补题 | √ | √ | √ | . |
2A. Difference Operations
$\text{Solution:}$
不妨从 $a_2$ 开始考虑，因为 $a_2$ 进行的操作只有减去 $a_1$，所以 $a_2$ 必须是 $a_1$ 的倍数，然后我们就可以将 $a_2$ 减去若干个 $a_1$ 后变成 $a_1$。
考虑 $a_3$ 及以后的数也是如此，所以序列满足条件当且仅当 $a_i$ 都是 $a_1$ 的倍数，其中 $2\le i\le n$。
2B. Difference of GCDs
$\text{Solution:}$
显然 $\gcd(i,a_i) \le \min(i,a_i)\le i$，又因为题目要求 $\forall 1\le i\le n$，$\gcd(i, a_i)$ 互不相等，所以 $\gcd(i,a_i)=i$。
那么只需在 $l\sim r$ 看有没有 $i$ 的倍数即可，否则输出 -1。
2C/1A. Doremy’s IQ
$\text{Solution:}$
场上被骗的一道题目，如果正向考虑，肯定是希望做减智商的测试越晚越好，但不容易实现。
那就反向考虑，设初始智商为 $0$，倒向做测试，遇到做不动的智商 $+1$，智商最多加到 $q$，这样如果我们遇到一个做不动的测试，但智商还没加到 $q$，那么我们一定要去做，因为智商越高，后面更有可能完成更多测试。
时间复杂度 $\mathcal{O}(n)$。
2D/1B. Difference Array
$\text{Solution:}$
不妨来证明暴力做法复杂度的正确性。
我们设每次操作后并忽略 $0$ 的 $a$ 数组总和为 $S$，$S=\sum\limits_{i=1}^ma_i$，且根据题意有 $\forall1<i\le m$，$a_{i+1}-a_{i}>0$。
$S=\sum\limits_{i=1}^ma_i\ge m-1+a_m$
那么差分一次后的数组变为 $a_2-a_1,a_3-a_2,\cdots,a_m-a_{m-1}$，现在的总和 $S’=a_m-a_1\le a_m$。
原本大于等于 $a_m+m-1$，现在小于等于 $a_m$，说明每次至少减少了 $m-1$，在第一次差分后，数组总和不超过 $a_n$，那么最坏情况的复杂度就为 $\mathcal{O}(A\log A)$，其中 $A=\max(n,a_n)$。
2E/1C. DFS Trees
$\text{Solution:}$
这题有个结论：如果 $\text{findMST(u)}$ 得到的生成树为最小生成树，那么图中没有交叉边。
关于交叉边的定义，我们可以用一个例子理解。
白边为生成树边，则红边为交叉边，而蓝边不是交叉边，即交叉边的最近公共祖先不为边的端点。
至于上面的结论为什么成立，现在还不太知道，先硬记一下吧。
那么对于每条非树边，如果能作为以 $u$ 为根的生成树的交叉边，那么 $\text{findMST(u)}$ 就得不到最小生成树。
我们以 $1$ 为根节点，跑出最小生成树，对于一条非树边 $(u,v)$：
- $lca=u$ 或 $lca=v$，那么以 $u,v$ 这条路径中间的点（不包括 $u,v$）为根，$(u,v)$ 就会作为一条交叉边，这些点都得不到最小生成树。
- 否则，那么从 $1$ 到 $u$ 的父节点和 $1$ 到 $v$ 的父节点的路径就全部得不到最小生成树。
最后统计答案即可，维护方法有很多，时间复杂度 $\mathcal{O}(n\log n)$。
Educational Codeforces Round 132$\text{(1709)}$
比赛时间：$\text{2022/7/21 22:35}$
| $\text{Penalty}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ |
|---|---|---|---|---|---|---|
| $112$ | $\texttt{+}$ | $\texttt{+}$ | $\texttt{+}$ | $\texttt{+1}$ | ||
| $\text{00:03}$ | $\text{00:16}$ | $\text{00:33}$ | $\text{00:50}$ | |||
| 补题 | √ | . |
A. Three Doors
$\text{Solution:}$
太难了，不会做。
B. Also Try Minecraft
$\text{Solution:}$
考虑记录一个前缀和后缀和表示到达某处的花费，然后就能 $O(1)$ 查询。
C. Recover an RBS
$\text{Solution;}$
考虑括号匹配的另一种理解：将左括号看作 +1，右括号看作 -1，保证所有前缀和大于等于 $0$，且总和为 $0$。
那么贪心地考虑，将左括号尽量地靠左，才能更有机会合法，那么我们找最优的两种即可。
D. Rorororobot
$\text{Solution:}$
先跳到当前列的最高处，判断移动的列之间是否有被挡住的地方，即维护静态区间最大值，用了 st 表，时间复杂度 $\mathcal{O}{(n\log n)}$。
E. XOR Tree
$\text{Solution:}$
记 $dist_u$ 表示 $1\sim u$ 路径异或和。
考虑 $(u,v)$ 之间路径的异或和 $dist_u\oplus dist_v\oplus a_{\text{lca(u,v)}}$。
可以证明如果只改变改变 $a_u$ 的取值，就能使以 $u$ 为根的子树不存在路径异或和为 $0$ 的点对。
我们可以对每一个节点开一个 set 表示以 $u$ 到 $u$ 子树内一点能表示出的所有的异或值，记为 $s_u$，然后对于 $u$ 的子节点 $v$，考虑是否有 $x\in s_u,y\in s_v,x\oplus y\oplus a_u=0$，如果存在，说明我们必须修改 $a_u$，修改后清空 $s_u$；如果不存在，将 $s_v$ 合并入 $s_u$。
最后用 dsu on tree，将复杂度优化至 $\mathcal{O}(n\log^2 n)$。
$\text{Code: }$Submission #165254294 - Codeforces
Codeforces Round #845 (Div. 2)$\text{(1777)}$
比赛时间：$\text{2023/1/21 22:35}$
| $\text{Score}$ | $\texttt{A}$ | $\texttt{B}$ | $\texttt{C}$ | $\texttt{D}$ | $\texttt{E}$ | $\texttt{F}$ |
|---|---|---|---|---|---|---|
| $4434$ | $496$ | $\texttt{972}$ | $\texttt{1374}$ | $\texttt{1592}$ | $\texttt{-4}$ | |
| $\text{00:02}$ | $\text{00:07}$ | $\text{00:21}$ | $\text{00:51}$ | |||
| 补题 | √ | √ |
又是一年除夕夜，又是一次上分场。
其中后两题用的算法贴合联赛知识点，不得不说是一场适合国人的良心场。
A. Everybody Likes Good Arrays!
$\text{Solution:}$
本题只要观察出 “奇 $\times$ 奇 $=$ 奇，偶 $\times$ 偶 $=$ 偶” 的性质后，直接统计相邻两数的奇偶性相同的对数即可。
时间复杂度 $\mathcal{O}(n)$。
B. Emordnilap
$\text{Solution:}$
我们将逆序对 $(i,j)$ 分为三类：$(i<j)$
- $1\leq i<j\leq n$
- $1\leq i\leq n,n+1\leq j\leq 2n$
- $n+1\leq i<j\leq 2n$
观察可知，对于 $n+1\leq i<j\leq 2n$ 的逆序对，一一对应一个 $1\leq i<j\leq n$ 的正序对，那么第一类和第三类的总数为 ${n\choose2}$。
而第二类是在序列的两边分开选的，因此对于 $p_i$ 来说，满足的 $j$ 有 $(p_i-1)$ 个，那么第二类的总数为 $\sum\limits_{i=1}^n(i-1)=\dfrac{(n-1)n}{2}$。
因此对于任何一个序列，逆序对数都是 ${n\choose 2} + \dfrac{(n-1)n}{2}=(n-1)\cdot n$，那么总数就为 $n!\cdot (n-1)\cdot n$。
时间复杂度 $\mathcal{O(n)}$。
C. Quiz Master
$\text{Solution:}$
观察到本题要求极差最小，如果你做过P7514 [省选联考 2021 A/B 卷] 卡牌游戏，那么就显然发现是一道双指针题。
本题不需要二分，对于左端点 $i$，找到第一个满足的右端点 $j$，更新答案，然后移动左端点至 $i+1$ 继续找即可。
判断合法的方法：维护一个桶，添加一个数就将它的所有因数扔到桶里，并统计有多少个桶是不空的，删除同理。如果前 $[1,m]$ 的桶不空，说明当前时刻合法。
时间复杂度 $\mathcal{O}(n\sqrt{n})/\mathcal{O(n\log n)}$ 。
D. Score of a Tree
$\text{Solution:}$
样例答案居然是 $32$ 的倍数！
这题我是这么考虑的，考虑拆贡献计算，对于一个节点 $u$，对于 $u$ 子树内的某一层（记为 $dep$），当且仅当在某一时刻 $t_0$（更具体地，$t_0=dep-dep_u$，即这一层的深度减 $u$ 节点的深度），$dep$ 这层上的节点同时合并到 $u$ 节点并贡献给 $u$ 一个 $0$ 或 $1$，不妨设这一层有 $sz$ 个节点。
我们尝试计数有多少种局面使得 $dep$ 这一层贡献 $u$ 时的答案为 $1$？根据 xor 的结合律，显然当 $sz$ 个节点中有奇数个 $1$ 时 xor 和为 $1$，那么这 $sz$ 个点的选择方案为 ${sz\choose 1}+{sz\choose 3}+{sz\choose 5}+\cdots=2^{sz-1}$，而剩余 $(n-sz-1)$ 个点可随意选择（注意我们统计的是初始 $n$ 个节点的局面数而不是单看这一层有多少种不同的局面），所以总局面数为 $2^{sz-1}\cdot 2^{n-sz}=2^{n-1}$。
此时观察样例确实是 32 的倍数。
那么对于节点 $u$，它子树内每一层都会对 $u$ 产生 $2^{n-1}$ 贡献，记 $f_u$ 表示 $u$ 子树内的最深深度，那么最终答案就是 $2^{n-1}\times \sum\limits_{u=1}^n (f_u-dep_u+1)$。
时间复杂度 $\mathcal{O}(n)$。
E. Edge Reverse
要求最大值最小，先二分一手去掉这个限制。
那么边权 $w_i\leq mid$ 的都变成了双向边，在这样的一张图上问是否存在一个节点能到达其它全部节点？
考虑先将所有双向边相连的点用并查集合并起来，因为此时并查集内的点相互可达。
然后变成了一张只包含有向边的图，我们在上面找到所有强联通分量，一个强联通分量内的点是相互可达的。
而注意到强联通分量缩点后的图是 DAG，那么存在一个节点能到达其它全部节点等价于 DAG 上只有一个入度为 $0$ 的点。
时间复杂度 $\mathcal{O}(n\log n)$。
好不容易看到一个最近刚学的算法结果写挂了，纯傻逼。
F. Comfortably Numb
我们可以借用笛卡尔树形结构理解。
对于一段区间 $[l,r]$ 的最大值下标 $p$，我们考虑 $i\in[l,p],j\in[p,r]$ 的答案贡献，此时 $i\sim j$ 的最大值已确定为 $a_p$。
那么问题就变成了 $sum_{i-1}\oplus sum_j\oplus a_p$ 的最大值是多少，由于对于 01-trie 上的查询复杂度稳定 $\mathcal{O}(\log 10^9)$，我们递归维护 $[l,p-1]$ 和 $[p+1,r]$ 的 trie 树，然后选择 $[l,p]$ 和 $[p,r]$ 较短长度的一边，枚举每一个下标，并在另一边的 trie 上查询即可。
因此最终实现时，我们先递归解决 $[l,p-1]$ 和 $[p+1,r]$，最后才能将左右 trie 树合并。
由于枚举的较短一边，可以证明最坏情况下的复杂度为 $\mathcal{O}(n\log n\log 10^9)$。
注意 trie 树中一些边界的点可能没有维护（如 $sum_{l-1},sum_p$），需要再单独贡献一次。
$\text{Code: }$Submission #190055840 - Codeforces (Unofficial mirror by Menci)