A
题意：给定 \(n\) 个三元组 \((x_i, y_i, t_i)\)，表示第 \(i\) 个人初始在位置 \((x_i, y_i)\)，需要花费 \(t_i\) 秒把手里的活干完。
现在选定一个集合地点 \((X, Y)\)，每个人干完手中的活立刻去集合，花费 \(\vert X - x_i \vert + \vert Y - y_i\vert\) 秒。最小化所有人都集合的时间。
形式化最终答案：
\[\max \bigg( t_i + \vert X - x_i \vert + \vert Y - y_i\vert \bigg) \]转为切比雪夫距离：
\[\max \bigg( t_i + \max(\vert X - x_i \vert + \vert Y - y_i\vert) \bigg) = \max \bigg( \max(\vert X - x_i \vert +t_i), \max(\vert Y - y_i\vert + t_i) \bigg) \]单独对一个坐标讨论：
- \(x_i \le X \implies X - (x_i - t)\)。
- \(x_i > X \implies (x_i + t) - X\)。
因此每个 \(i\) 生成两个新点 \(x_i - t, x_i + t\)，\(X\) 在数轴上移动，最小化最大距离，显然是 \(\dfrac{\max (x_i + t) - \min(x_i - t)}{2}\)。
这么做为什么是对的？
如果 \(x_i + t > X\)，\(i\) 的贡献会取到 \((x_i + t) - X\)，如果 \(x_i < X\)，\(X - (x_i - t) > (x_i + t) - X\)，不会用到 \((x_i + t) - X\) 这个非法的值。
其他情况同样讨论。submission
一个不需要额外考虑的做法：二分答案，把答案减掉 \(t\) 后以 \(x\) 为中心可以确定 \(X\) 范围，看最后交集是否为空。
B
题意：
C
题意：给定一棵 \(n\) 个点的有权树，\(q\) 次修改，每次询问 \(\sum_i\sum_{j > i} [c(i, j) = 1]\)，其中 \(c(i, j)\) 表示 \(i \to j\) 的路径上所有边权的 gcd。
\(n \le 10^5, q \le 100\)。
设值域为 \(m\)，有莫比乌斯反演：
\[\begin{aligned} \sum_{i < j} \sum_{d \mid c(i, j)} \mu(d) &= \sum_{d = 1}^m\mu(d) f(d)\\ \\ f(d) &= \sum_{i, j}[d \mid c(i, j)] \end{aligned} \]其中 \(f(d)\) 可以理解为只含边权为 \(d\) 的倍数的边的图上互相连通的点对数。由于影响是持续的，这个东西显然可以在时间轴上分治。
一条边权为 \(i\) 的边会加到所有 \(d \mid i\land \mu(d) \ne 0\) 的因子的图里，最多 \(2^{w(i)}\) 种，其中 \(w(i)\) 表示 \(i\) 的本质不同质因子个数。
枚举 \(d\)，把 \(f(d)\mu(d)\) 贡献到 \(0 \sim q\) 的每个时间点。
记 \(s = 2^{\max w(i)}\) 表示一条边最多加到多少个因子，则时间复杂度 \(O\big((n + q)s\log q + q\log n\log q\sum_{d}[\mu(d) \ne 0]\big)\)，\(\log n\) 是可撤销并查集的复杂度。
冲到了线段树分治最优解。submission
D
题意：
标签：13,vert,max,sum,CSP2024,mu,bigg,题意 From： https://www.cnblogs.com/Luxinze/p/18393565