题意

给定一棵树，边权带修，强制在线，询问直径。

其中 $3 \le n, q \le 10^5$。

分析

首先，给出一个引理：树上的两个点集 $A,B$，点集 $A$ 的某一条直径端点 $a_1,a_2$，点集 $B$ 的某一条直径端点 $b_1,b_2$，则两个点集之间的直径一定是这 $4$ 个点中最长的距离。反证法，容易证明。

树状数组和 LCA 解决带修路径长度。线段树维护区间的直径和直径端点。

对于修改操作，先修改边权，然后线段树上重构可能跨过这条边的线段树区间直径。

记修改边的深度大的结点为 $u$，注意到 $u$ 的 dfs 序区间内的直径一定不变，以及外部的区间一定不变，这个过程等价于在线段树上 dfs 了 $u$ 的 dfs 序区间，重构一下经过的所有结点。

时间复杂度 $O(n\log n + q \log ^2 n)$。

回到梦（题解）开始的地方？

A XORinacci

B Uniqueness

C Magic Grid

用 $[0,n^2-1]$ 填一个 $n \times n$ 的矩阵，使得每行每列异或和相同，其中 $n$ 是 $4$ 的倍数。

不知道为啥，反正观察出四个填一个 $2 \times 2$ 就行了。

D Restore Permutation

有一个排列 $p$，现在你知道对于位置 $i$，排列上前 $i-1$ 个数小于 $p_i$ 的和为 $s_i$，要求恢复出 $p_i$。

从后往前，在树状数组上二分即可。

E Let Them Slide

最大长度为 $w$，给定 $n$ 个滑动窗口，每个窗口有 $l_i$ 个数，回答 $w$ 个独立询问，所有窗口任意滑动，第 $i$ 列的最大权值和。

差分答案。

枚举每一行，枚举整个值域范围，对于位置 $i$，他可能是从窗口中某一个范围转移过来，注意到，如果窗口很短，那么中间会有很多位置只由窗口最大值贡献而来，那么我们实际上只需要枚举值域范围某个前缀和后缀，中间一部分可以在差分数组上打标记。如果窗口很长，即长度大于 $w \over 2$，那么这样的窗口最多出现 $2$ 个，因此总复杂度为 $O(\sum l_i)$。

A There Are Two Types Of Burgers

B Square Filling

天道有轮回，$n,m$ 打反饶过谁？

C Gas Pipeline

有一段长度为 $n$ 管道，给定一个 $01$ 编码，$1$ 表示这一段管道高度为 $2$，否则可以为 $1$ 或 $2$。

$n+1$ 个端点，每个端点上设置支架，$n$ 段管道，可能在某些位置被抬高，管道单价为 $a$，支架单价为 $b$，最小化总费用。

枚举中间的每一段低处是否被完全抬起费用更低。

D Number Of Permutations

给定一个二元组的序列，求有多少种排列方式，使得两个二元组的两个维度均不单调不减。

容斥，总排列数减去分别单调和偏序单调的方案数，类似于多重集的排列。

E XOR Guessing

有一个数字 $x$，询问两次，每次询问有 $100$ 个数，返回 $x$ 和某一个询问值的异或。

第一次，询问 $1$ 到 $100$，第二次询问 $1$ 到 $100$，每个乘上 $2^7$，即第一次询问低 $7$ 位，第二次询问高 $7$ 位。

F Remainder Problem

单点更新，询问模 $x$ 余 $y$ 所有位置的和。

根号分块，模数小的，维护答案，模数大的，有贡献的位置不超过 $\sqrt{n}$。

G Indie Album

输入一个 Trie，每次询问一个输入串 $T$ 作为 Trie 上的第 $i$ 个结点的子串出现次数。

考虑都是一个串的情况，可以枚举母串的前缀在询问串 AC 自动机上的匹配结点，如果匹配点在 $fail$ 树上，到根的路径里经过询问串终点，那么当前前缀的一个后缀是询问串。

多串的情况就是在原 Trie 上 $dfs$，对询问串建 AC 自动机，维护 AC 自动机的匹配结点，单点更新，子树查询和。