Day1 A. Waterloo Tag
\(x\) 跑一个最短路，Roger 就是要在不被提前抓到的情况下走到一个 \(dis\) 尽量大的位置并一直等待（可以在边上）。
此时到达 Roger 到达每个点的时间也是越早越好，所以对 Roger 来说一样的可以跑一个最短路，不过最短路需要保证到达的点和走过的边都不会被抓住，这个可以直接推下式子（相遇和追及两种情况）算出时间比较一下。
因为对于一条边的 \(dis\) 是一个单峰函数，如果 Roger 能走到峰则肯定取峰的值，否则取走到的最远的值（因为这部分在向峰走的过程中，走的越远 \(dis\) 也就越大）。
时间复杂度 \(\mathrm{O}(nm\log m)\)。
Day1 B. Melborp
对 \(i\) 来说，合法的 \([l, r]\) 应该都是一个大区间 \([l_{i}, r_{i}]\) 的子区间。其中 \(l_{i}\) 满足 \(l_{i} = 1\lor a_{l_{i} - 1} < a_{i}\) 且 \(j\in [l_{i}, i], a_{j}\ge a_{i}\)，\(r_{i}\) 是类似的。对应的区间数就为 \((i - l_{i} + 1)(r_{i} - i + 1)\)。
取 \(i = 1\)，因为此时 \(l_{i}\) 只能为 \(1\)，就推出来了 \(r_{1}\) 的值。此时知道的信息是 \(a_{r_{1} + 1} < a_{i}, \forall j \in[2, r_{1}], a_{j}\ge a_{i}\)。
此时考虑 \(a_{2}\) 和 \(a_{1}\) 的大小，如果 \((r_{1} - 2 + 1)(2 - l_{1} + 1)\) 为 \(a_{2}\) 的区间数，那么对应的区间也相同，有 \(a_{1} = a_{2}\)；否则 \(a_{1} < a_{2}\)，那又知道了 \(l_{2} = 2\)，又解出来了 \(r_{2}\)，看起来就可以递归处理了。
于是考虑一个函数 \(\operatorname{solve}(i)\)，调用前已知 \(i\) 的信息，最后要求出 \((i, r_{i}]\) 的信息。 记 \(j = i + 1\)：
- 若 \(j > r_{i}\)，则已完成不需要处理了。
- 若 \((r_{i} - j + 1)(j - l_{i} + 1)\) 是 \(a_{j}\) 的区间数，则 \(l_{j} = l_{i}, r_{j} = r_{i}, a_{j} = a_{i}\)，可以递归至 \(\operatorname{solve}(j)\) 然后就不用考虑了。
- 否则考虑 \(a_{j}\) 应该是 \(> a_{i}\) 且 \(< a_{k}(k\in (i, j))\)，那么 \(l_{j} = i + 1\)，可以解出来 \(r_{j}\)，递归至 \(\operatorname{solve}(j)\)，然后继续向后处理 \(j\gets r_{j} + 1\)。
最外层需要做一个类似 \(\operatorname{solve}(0)\) 的过程。
这其实就是小根笛卡尔树不断从 \(i + 1\) 向上跳的过程。
知道了 \(l_{i}, r_{i}\) 后就好构造了，按照区间长度从大到小排序依次填数，注意区间相同数也要相同即可。
时间复杂度 \(\mathrm{O}(n)\)。
Day1 C. Beyond Counting
区间数种类数就不太简单，大概还是得用一个根号做法。
对次数根号分治，出现次数 \(> \sqrt{n}\) 的做树上前缀和后直接统计即可。
出现次数 \(< \sqrt{n}\) 的，离线情况下比较好的做法就是直接树上欧拉序莫队处理。
强制在线就相当于是要做一个在线莫队，序列上的做法是每 \(\sqrt n\) 个点放一个关键点，先维护下关键点信息，再从关键点信息向外扩张 \(\mathrm{O}(\sqrt n)\) 步。 树上也是类似的，考虑随机撒点，或者说是深度按 \(\bmod \sqrt{B}\) 分类，选类中点数最少的一类点做关键点，这样任意两点到关键点距离均是 \(\mathrm{O}(\sqrt n)\) 的，且关键点数是 \(\mathrm{O}(\sqrt n)\) 的。
时间复杂度 \(\mathrm{O}((n + q)\sqrt n)\)。
好像有点太难写了，我没写。
Day2 A. Asymmetry
考虑到这个贡献是列对称的，且每个列会被恰好一次，所以很自然的想法就是应该把对称的两列单独考虑，每一组一定是 Alice 先操作 Bob 再操作对应的另一列。 证明考虑若 Bob 没有操作 Alice 操作的那列，则 Alice 把 Bob 操作的位置对称的位置改成相同的值明显 Alice 更优了且这个过程还会进行下去（可以看作后手永远都不劣于先手劣，而 Bob 这样做相当于是交换了先后手）。
于是现在转为了 \(m = 2\) 的情况，考虑枚举 Alice 操作的列，记为 \(a_{1\sim n}\)，另一列记为 \(b_{1\sim n}\)。
只考虑答案的增量，那么 Alice 选择把 \(a_{i}\) 改成 \(v\) 会产生 \(|v - b_{i}| -|a_{i} - b_{i}|\) 的增量。再考虑 Bob，对于 \(a'_{i}, b_{i}\)，Bob 要使绝对值差最大，那么 \(b_{i}\) 一定为 \(0\) 或 \(K\)，会产生 \(\max(a_{i}, K - a_{i}) - |a_{i} - b_{i}|\) 的增量，Bob 则会选之中最大的一个。
单独对 \(i\) 考虑，记其余 \(j\) 的 \(\max(a_{j}, K - a_{j}) - |a_{j} - b_{j}|\) 的最大值为 \(mx\)，则 \(i\) 改成 \(v\) 对 Alice 的增量是 \(|v - b_{i}| - |a_{i} - b_{i}| + \max(mx, \max(v, K - v) - |v - b_{i}|)\)。
忽略 \(-|a_{i} - b_{i}|\) 这个常数项，并把 \(|v - b_{i}|\) 加入到 \(\max\) 中去，变成 \(\max(mx + |v - b_{i}|, v, K - v)\) 的形式。
不妨假设 \(b_{i} < K / 2\)（若 \(b_{i} > K / 2\) 则让 \(a_{i}, b_{i}\) 同时变为 \(K - a_{i}, K - b_{i}\) 无影响），分讨 \(\max\) 内部的情况：
- \(v \le b_{i}\)，则为 \(\max(mx + b_{i} - v, K - v)\)，\(v = b_{i}\) 时最小。
- \(b_{i}\le v\le K / 2\)，则为 \(\max(mx + v - b_{i}, K - v)\)，\(v = \frac{b_{i} + K - mx}{2}\) 时最小。
- \(K / 2\le v\)，则为 \(\max(mx + v - b_{i}, v)\)，\(v = K / 2\) 时最小。
因为实际 \(v\) 只能取整数，所以要注意一下取整的问题。
时间复杂度 \(\mathrm{O}(nm)\)。
Day2 B. Tree Traversals
小巧思题目（做出正解的时候感觉很荒诞，挺好的题）。
没时间了明天写。
Day2 C. Walking on a Graph
没时间了明天写。