A：

爆搜可以拿到前 25 分。

考虑生成树的结构。设所有在树中的形如 $(i,i+n)$ 的边分别为 $(a_1,a_1+n),(a_2,a_2+n),\ldots,(a_k,a_k+n)(a_1<a_2<\cdots<a_k)$ 。容易发现生成树中一定包含 $(1,2),(2,3),\ldots,(a_1-1,a_1)$ 与 $(n+1,n+2),\ldots,(n+a_1-1,n+a_1)$ 这些边。对于 $a_k$ 到 $n$ 的部分同理。对相邻的 $a_i$ 与 $a_{i+1}$ 之间，除恰好一条边外，$(a_i,a_i+1),(a_i+1,a_i+2),\ldots,(a_{i+1}-1,a_{i+1})$ 与 $(n+a_i,n+a_i+1),\ldots,(n+a_{i+1}-1,n+a_{i+1})$ 都在树中。称 $a_i$ 与 $a_{i+1}$ 之间为一段。

可以发现，一条横着的边（网格中形如 $(i,i+1)$ 的边）的贡献只与它所在的段缺少的边有关，一条竖着的边（网格中形如 $(i,i+n)$ 的边）的贡献只与两端的段中缺少的边有关。所以可以设计出一个简单 dp：令 $d_{i,0/1}$ 表示当前段中缺少的边是 $(i,i+1)/(n+i,n+i+1)$ ，每次转移时枚举上一条竖着的边和上一段中缺少的边即可，进一步观察可以发现，竖着的边的选取是凸的，直接在枚举上一段中缺少的边时，双指针更新竖着的边的最优位置，就可以做到 $\mathcal O(n^2)$。

B：

场上没怎么看题。

考虑合法括号序列的一个左右两个括号匹配的合法子串，若分界点（也就是第一个偶数位置）在子串内部，那么一定会同时选出该括号序列的左右两个括号，所以分界点不能在它们内部。

所以如果将括号序列中的 ( 看作 $1$，) 看作 $-1$，分界点只可能在前缀和为 $0$ 的下下个位置（或者不存在），且这些位置显然合法（前后缀影响独立），所以合法括号序列的权值为前缀和为 $0$ 的位置个数 $+1$ 。

进一步可以发现，翻转区间 $[l,r]$ 对前缀和数组 $s_i$的影响是：$s_{1\cdots l-1}$ 不变，$s_{l\cdots r}$ 按 $x=k$ 对称，$s_{r+1\cdots 2n}$ 平移 $c$ 个单位，其中 $c$ 和 $k$ 可由 $s_{l-1},s_r$ 计算得出。

最终需要支持区间加，区间乘 -1，询问区间最值，区间最值个数，线段树实现即可。

若全局最值 $<0$ 或 $s_{2n} \not = 0$，则括号序列不合法。时间复杂度 $\mathcal O(n+q\log n)$，可以通过此题。

C：

不难发现，每个时刻只需要考虑当前存在的区间中，不包含任何其他存在区间的那些区间。容易发现这样的区间按照左端点排序后右端点也有序。现在考虑维护出每个这样的区间中，有多长的路段未被工作过，每次从中选择最小的一个就可以了，可以用线段树维护。

现在考虑如何维护未被工作过的路段长度。

首先离散化，显然可以每次只将离散化后相邻的点之间的区间标记为已被工作（最多标记 $n$ 次）。

由于区间的性质，每次标记时，一定是一段区间中的工人覆盖了这一小段。用线段树做区间减，查询最小值位置即可。

接下来考虑如何维护不包含任何其他区间的区间集合，相当于每次动态删除一个区间，要求出有哪些新的区间变成了不包含任何其他区间的区间。一种简单的方法是用线段树优化建图，建出一个 DAG，类似拓扑排序，每次删除一个区间时，更新即可。

需要维护一棵线段树，维护哪些路段未被工作，用来查询新出现的工人当前工作的工作量。

应该还可以单独维护所有被包含的区间，不太懂。

时间复杂度 $\mathcal O(n\log n)$ 。