集训模拟赛的题解应该都在 CWOI 杂题里。
主要就是题目的记录？不太想写游记。
简单题不会写。
7.7
考试，考得依托。
7.8
很趣味的数据结构！
感觉很有集训那味啊，就是前面讲一会简单的东西然后突然上强度。
gym100739E. Life as a Monster
还是挺简单。套路地把切比雪夫距离转成曼哈顿距离，然后做完了。
主要难点是卡空间。你可以用平衡树，\(\mathcal{O}(n)\) 的空间；或者你可以动态开点线段树，但是要注意在 int mid=(l+r)>>1 的时候 l+r 会爆 int（如果你有这个错误，大概会 mle on test 5）。
对了，\(T\) 记得及时膜 \(BASE\)，不然 a1*T 会爆 long long（如果你有这个错误，大概会 wa on test 19）。
CF319E. Ping-Pong
考虑两个区间
CF487E. Tourists
因为题目要求不经过重复点，我们考虑点双。根据点双的定义，我们路径上经过的所有点双，它们里面的最小值是可以取到的，所以你考虑把它缩点。
但是点双是会重点的，不能直接缩。我们考虑一种叫圆方树的结构——对于所有点双，建一个对应的虚拟点，称为方点；把这个点双里的所有点全部向这个点连边，称为圆点。显然方点与方点间由圆点相连，这就构成了一棵树。
对这棵树树剖，定义圆点权值为题目中所给，方点权值为它对应点双内所有点权值最小值，原问题等价于求这棵树对应路径上经过的所有点的点权最小值。直接这么写在修改时不太好做，因为你需要修改包含它的所有方点。我们考虑略微修改一下方点点权的定义——修改为它所有儿子的点权最小值。这样每次修改点权时只用改它父亲这一个方点了。可以对每个方点开 multiset 来维护。
有一种特殊情况需要考虑：当 \(u,v\) 的 \(\text{lca}\) 为方点时，需要再考虑 \(fa_{\text{lca}(u,v)}\) 的点权。
CF1284D. New Year and Conference
假设 a 区间不交，b 区间相交，你可以开一棵线段树，维护 \(eb_j=i\) 的所有 \(j\) 中 \(sa_j\) 的最大值和 \(ea_j\) 的最小值。枚举一个区间，区间查即可。时间复杂度 \(\mathcal{O}(n\log n)\)。
当然，有一个更加牛逼的做法。维护集合 \(A\)，里面的二元组 \((i,j)\) 表示 \([sa_i,ea_i]\) 和 \([sa_j,ea_j]\) 有交，\(B\) 同理。你只需要判断 \(A\) 和 \(B\) 是否相等即可，这个可以 hash。时间复杂度也是 \(\mathcal{O}(n\log n)\)，瓶颈是排序/离散化。
7.9
CF1149C. Tree Generator™
从直径的求法入手。一个最显然的想法是两次 dfs 求直径，可惜它行不通。
不妨转化一下思路：直径等价于树上最长的一条路径。对于一条路径 \((u,v)\)，\(\text{dist}(u,v)=d_u+d_v-2d_{lca}\)。这跟括号序列有什么关系？对于两个点 \(u,v\)，设它们在括号序列中对应点为 \(l,r\)，那么 \(d_{lca}=\min\limits_{i=l}^r\{d_i\}\)。所以求直径等价于在括号序列里求三个点 \(x\le y\le z\) 使得 \(d_x+d_z-2d_y\) 最小。
显然三个数同时加减一个数对答案没有影响，所以我们可以只用考虑在这个区间内每个位置的深度（左右括号对应 +1/-1，深度就是前缀和），像维护最大子段和一样维护一下相关信息转移即可。