T1

100%

考场编号实际上就是 $\lceil \frac{n}{30} \rceil$，可以通过 $\frac{n-1}{30}+1$ 得到。

座位编号为 $((n-1) \mod 30) +1$

时间复杂度 $O(1)$ 。

T2

100%

由于 $n \leq 1000$ ，我们可以枚举每个起点，然后检查从该起点开始的长度为 $k$ 的环形子数组是否符合要求。判断是否为 $1 \sim k$ 的全排列，可以通过一个标记数组来标记出现过的 $\leq k$ 的数，并检查是否每个数都出现过即可。

时间复杂度 $O(nk)$ 。（可以通过滑动窗口的方式实现 $O(n)$）

T3

100%

首先可以通过一次遍历可以计算出每个位置是否是峰顶（或谷底），可以设 $s[i]=1$ 表示 $i$ 位置为峰顶，需要多次询问区间内的峰顶数量，即查询 $s$ 数组在区间内 1 的个数，对 $s$ 数组做前缀和即可 $O(1)$ 查询。

注意查询区间 $[l,r]$ 时，实际需要统计的位置应为 $[l+1,r-1]$，必须保证 $l+1 \leq r-1$，即 $l = r$ 时需要特判。

时间复杂度 $O(n)$。

T4

100%

首先由于每个点的深度给定，因此树上每一深度所拥有的点是固定的，我们需要给每个点找一个父亲节点，使得最终的父亲数组 $p_1,p_2,\dots,p_n$ 的字典序最小。

然后考虑一个点 $i$ （深度 $d_i$），对于所有深度为 $d_i -1$ 的点，一定从中选择编号最小的且当前儿子个数未满的点作为 $p_i$；

其次对于同一深度的所有点，一定是编号越小的点先选择父亲，因为编号小的点在序列中更靠前，因此更需要选择编号更小的父亲。

综上，我们需要对所有点按深度排序，深度相同按下标排序，然后依次给每个点选择一个父亲，选择父亲时尽可能选择上一深度中编号最小的且还能选择的点。

然而暴力查找每个点的父亲最坏需要 $O(n^2)$ 的时间复杂度，可以利用双指针的思想，记录上一深度当前能选择的父亲的位置，每次被选择后更新该父亲的儿子个数，若儿子个数已满，则指针向后移动至下一个可选择的父亲，因此上一深度的每个点最多只会被枚举一次，时间复杂度降为 $O(n)$。

总的时间复杂度为 $O(n)$。

T5

100%

由于所有点的运动区间长度相同，均为 $L$，所有点的运动周期为 $2L$，因此可以先令 $t'=t \mod 2L$，然后可以将所有点分成两组：初始方向向右的和初始方向向左的。方向向右的所有点最终位置会 $+d$，方向向左的所有点最终位置会 $-d$，其中：

$$d= \begin{cases} t' & \text{如果 }t' \leq L \\ 2L-t' & \text{如果 }t' > L & & \end{cases}$$

接下来我们就需要求两个数组，分别整体加上或减去同一个值 $d$，然后求这两个数组归并后的第 $k$ 小值。

一个做法是可以先二分第 $k$ 小的值 $ans$，然后判断 $\leq ans$ 的个数是否达到了 $k$，判断的过程可以在两个有序数组中分别二分即可求出 $\leq ans$ 的个数，单次查询的时间复杂度 $O(\log V \log n)$ ，$V$ 为值域。

另一个实现稍复杂但更快的做法是直接在其中一个有序数组中二分取的个数 $x$，那么另一个数组中取的个数即为 $k-x$，想要让这 $k$ 个数作为前 $k$ 小，那么就必须保证第一组取出的最大值 $\leq$ 第二组未取的最小值，反之亦然。单次查询的时间复杂度为 $O(\log n)$。

T6

100%

直接枚举所有对 $(u,v)$ 并计算 $\text{lcp} (u,v)$ 是困难的，但我们可以按贡献分解：

$$\operatorname{lcp}(u,v)=\sum_{L=1}^\infty\mathbf{1} [u和v的前L个字符相同] $$

因此原式：

$$\sum_{u\in S}\sum_{v\in S}\mathrm{lcp}(u,v)=\sum_{u,v}\sum_{L=1}^\infty\mathbf{1}[u,v\text{ 前 }L\text{ 相同}] $$

交换两个求和符号的顺序：

$$=\sum_{L=1}^\infty\left(\sum_{u,v}\mathbf{1}[u,v\text{ 前 }L\text{ 相同}]\right) $$

固定一个长度 $L$，内层的 $\sum_{u,v}\mathbf{1}[\dots]$ 实际是要求有多少对 $(u,v)$ 使得他们的前 $L$ 个字符完全相同。

然后我们可以按实际内容分组：对所有可能的长度为 $L$ 的序列 $P$，统计有多少子序列 $u$ 以 $P$ 为开头，记个数为 $cnt(P)$，那么满足“前 $L$ 个字符都是 $P$”的 $(u,v)$ 的对数就是 $cnt(P) \times cnt(P) = cnt(P)^2$。

把所有可能的 $P$ 加起来：

$$\sum_{u,v}\mathbf{1}[u,v\text{ 前 }L\text{ 相同}]=\sum_{P\text{ 长度为 }L}\operatorname{cnt}(P)^2 $$

最终原式即可转化为：

$$\sum_{u,v}\operatorname{lcp}(u,v)=\sum_{L=1}^\infty\sum_{P\text{ 长度为 }L}\operatorname{cnt}(P)^2 $$

右边其实就是所有可能的前缀 $P$ 的出现次数平方之和。

接下来我们需要求所有可能的前缀 $P$ 的个数以及每个前缀的出现次数。

对所有非空子序列 $P$ 按照结束位置分组（结束位置相同的 $P$ 作为前缀出现的次数是相同的）。设 $f[i]$ 表示恰好以 $i$ 位置为结尾的非空子序列个数，转移时考虑以 $i$ 为结尾的子序列的上一个位置：

$$\mathrm{f}[i]=\sum_{j=\mathrm{prev}[i]}^{i-1}\mathrm{f}[j] $$

其中 $prev[i]$ 为上一个 $a[i]$ 出现的位置（第一次出现则为 $0$ ），再往前的位置无需转移，因为以 $prev[i]$ 为结尾和以 $i$ 为结尾的序列会产生重复的子序列。

转移可以通过前缀和优化为 $O(1)$。

现在我们求出了恰好以 $i$ 位置为结尾的非空子序列个数 $f[i]$，接下来要求以这 $f[i]$ 个子序列作为前缀的子序列个数，即从位置 $i+1$ 开始的后缀数组中的所有不同子序列（包含空序列）。

类似地，可以从后往前dp，设 $g[i]$ 表示恰好以 $i$ 位置为开始的非空子序列个数，并做后缀和后，$suf[i+1]$ 即为从位置 $i+1$ 开始的后缀数组中的所有不同子序列。

最后答案：

$$\mathrm{Ans}=\sum_{i=1}^n\mathrm{f}[i]\cdot\left(suf[i+1]\right)^2 $$

时间复杂度为 $O(n)$。