A

对于一个子矩阵 \((x_1,y_1),(x_2,y_2)\)，其元素和为 \(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}S_i\cdot S_j=(\sum_{i=x_1}^{x_2}S_i)(\sum_{j=y_1}^{y_2}S_j)\)，\(O(n^2)\) 枚举一下 \(S\) 的所有子区间的和放进一个桶里再检验一下即可。

即对于一个子区间和为 \(S_1\)，需要累加和为 \(\frac{T}{S_1}\) 的子区间个数到答案中。特殊地，\(S_1=0\) 或 \(T=0\) 的时候需要一些特殊处理。

使用 unordered_map，\(O(n^2)\)。

B

注意到 \(S[l:r+1]\) 的字典序大于 \(S[l:r]\)，于是每次找到的都是 \(S\) 的后缀，那么就可以用哈希+二分来比较两个后缀的字典序大小，每次暴力找字典序最大的后缀，做到 \(O(n^2\log n)\)。

删去一个后缀后，剩余串的后缀之间的大小关系与删前原串的对应后缀的大小关系不变，那么接下来从后往前逐个考虑每个后缀，如果 \(S[i:]>S[j:]\) 且 \(i<j\)，那么最优策略中不会选择 \(j\) 这个后缀，于是用单调栈完成这个过程就可以找到过程中会选择的所有后缀了，只需要进行 \(O(n)\) 次大小比较，使用哈希+二分做到单次比较 \(O(\log n)\)。\(O(n\log n)\)。

C

首先我们不关心每次操作选择的 \(i,j\) 是如何配对的，只关心逆时针旋转的次数要等于顺时针旋转的次数。于是可以直接设计 dp 状态 \(f_{i,j}\) 表示考虑了前 \(i\) 个学生，并且有 \(j\) 个“不成对”的操作时得到的最大总幸福度，\(j>0\) 表示多出了 \(j\) 次顺时针，\(j<0\) 表示多出了 \(-j\) 次逆时针，每次转移的时候枚举 \(i\) 顺逆时针旋转的次数就可以完成转移。

这样做的问题在于，\(j\) 这一维的大小没有很好的控制，但是可以观察到 \(j\) 的“有效范围”在 \((-m,m)\) 之间，因为若 \(|j|\ge m\)，比如 \(j\ge m\)，那么我们对任意一个元素进行 \(m\) 次逆时针操作就可以使 \(j\) 减小 \(m\) 而不改变答案，\(j\leq -m\) 同理。于是这样就得到了一个 \(O(nm^2)\) 的做法。

实现上，又注意到 \(k\) 次顺时针可以用 \(m-j\) 次逆时针代替，所以 \(j\) 可以控制在 \([0,m)\) 内且转移时只考虑顺时针旋转的次数，常数会比较小。

D

如果只是维护每次插入的位置而不删除，可以使用 std::set \(S_1\) 维护极长连续空白段的信息，本题中要求按照长度从大到小排序，仍然可以用其维护，每次插入取出符合题意的一段并放入新的两段（如果存在）。再配合动态开点线段树/离散化之后树状数组或线段树，就可以完成员工不会离开的部分分。

对于删除操作，额外记录每个员工外套的位置，再开一个 set \(S_2\) 存这些位置，查询需要删除的位置在这个 set 中的前驱后继就可以找到 \(S_1\) 中对应的区间完成删除与合并的操作了。

要回答区间有多少个有效点，只需要用动态开点线段树。\(O(q\log n)\)，可以参考 std 实现。

E

如果不能瞬移，那么答案是 \((2\sum w_i)-L\)，其中 \(L\) 是直径长度。这很好理解，因为可以任选起点终点，这之间的边可以不经过第二次。

如果可以瞬移，类似地，这次瞬移可以让一些边不经过第二次，发现等价于选两条边集不交的链 \(P_1,P_2\)，其并集中的边可以只经过一次，那么只需要最大化这两条链的并集的边权和。如果边集有交，可以手玩发现其中一定有边被经过两次，而在唯一点相交是没有问题的。接下来只需要分两种情况：

• \(P_1\cap P_2=u\)，枚举点 \(u\)，等价于找四条从 \(u\) 出发的边不交的链使得边权和最大。记 \(dp_{u,i}\) 表示 \(u\) 第一步向不同的儿子走，能取到的第 \(i\) 长的链，转移只需要暴力合并一下。但是这没有考虑到向父亲走的情况，于是再记一个 \(f_u\) 表示 \(u\) 向上走的最长链，计算 \(f_u\) 时用父亲的信息合并一下即可。
• \(P_1\cap P_2=\varnothing\)，枚举点 \(u\)，选择 \(u\) 子树内和子树外的最长链，即两个连通块里的直径问题。子树内是好做的，子树外仍然是先从父亲继承，再用经过父亲的答案更新。这里实现上需要关注 \(v\) 的子树外答案分为 \(u\) 的子树外与 \(u\) 的子树内但 \(v\) 的子树外两部分，后者需要精细处理一下。注意，\(fa_u\) 与 \(u\) 之间的边可以用瞬移做到一次都不被经过，相当于对这两个连通块分别做不瞬移的问题，所以还需要额外统计此贡献。

总复杂度 \(O(n)\)，可以参考 std 实现。