A 大佬的难题

首先这题本身是一个裸的三维数点，直接做复杂度 $O(n\log^2 n)$ ，虽然各种卡常导致看起来随机数据是可以进 2.5 的，但是终测性能太差还是卡掉了！

我们考虑一个容斥。我们考虑对三个序列两两求一次二维偏序问题，这个问题复杂度显然是 $O(n\log n)$ 的。然后考虑对于一对 $i,j$ ，设满足偏序关系的维度数是 $k$ 。如果 $k = 0,k = 3$ ，它的贡献显然都是 $3$ ，也就是三次求二维偏序都把它算进去了。如果 $k = 1,k = 2$ ，那么它的贡献就是 $1$ 了，显然只有一次偏序会把它算进去。

那么我们直接把这个值减去 $\binom n 2$ 再除以 $2$ ，即可做到 $O(n\log n)$ 解决问题！

这题的优化思路很想之前见过的一个 JOI 的题，大概是数 $x \le a, y\le b,x+y \le c$ 的点的个数，但是是真的数点，这个东西容斥之后会发现有真正三个条件需要都满足的部分一定是 $0$ 。

B 回文串

非常难写的题，但是思路比较简单。

我们先离线考虑建立出两个 PAM ，分别是维护每个位置的最长回文后缀和反串的最长回文后缀。

然后对两个树分别树链剖分一下，然后现在就只需要考虑两个点来说，它们在树上的路径上的所有点了。因为我们考虑一下会发现，这个 transl 操作实际上就是把第一个串删得只剩最长公共后缀，再补回第二个串。这个东西所遍历到的所有回文串，其实在回文树上正好会形成一条路径。唯一需要特殊讨论的就是这个路径的 LCA 处的回文串是否应该被取，这个串是否被取取决于这个串的长度的两个串的 LCS 的长度的大小关系。

然后考虑在离线后，每次往后或者往前添加意味着什么。显然往前和往后添加最多都只会增加一个回文串。往后添加所得到的回文串在回文树上的位置是显然的，而往前添加的时候，其实得到的位置也是可以计算的。具体来说，我们考虑同样维护一个前 last 表示上次往前添加在回文树的位置，然后跳 fail 的时候，由于回文串是对称的，同样是可以判断当前这个回文往前添加字符是否是回文的。

然后再给一个位置加一后，我们需要给这个点到根的链全部加一，但是每个点都有一个自己的系数（就是这个点回文串的长度），一个点的真正权值是这个点的系数乘以值，这个东西也是一个经典问题，直接线段树打 lazy tag 即可。

复杂度 $O(n\log^2 n)$ 。

C 营养餐

好题

考虑一条链的情况，同时 $b_i = 1$ 的情况。由于一个点的合法的条件是 $a_i \ge a_{i + 1}$ ，我们不妨直接令 $c_i = a_i - a_{i + 1}$ ，然后就变成了每个点的权值 $\ge 0$ 。再考虑操作，一次操作在这里会正好导致这个点权值减少 $1$ ，它的前一个点的权值 $+1$ 。可以发现这个东西就是一个阶梯 Nim 游戏！

阶梯 Nim 是的结论是，我们只需要把奇数堆的石子拿出来做一次普通 Nim 即可。因为我们考虑，在当前的先手把偶数堆的石子移动到奇数堆时，显然后手一定可以通过把刚刚移动过的石子继续往后移动来消除先手造成的影响。那么如果先手发现当前只看奇数堆的时候先手必胜，那么一定会把情况变成奇数堆先手必败，然后让后手操作，后手如果不操作奇数堆，先手就直接去消除影响即可。

然后我们考虑扩展到树上的情况，树上的情况其实可以直接看成把深度为奇数的点拿出来做，证明和刚刚是一样的。

那么现在来考虑一下 $b_i$ 不一定等于 $1$ 的情况。我们让 $c_i = a_i - \sum_{v \in child} a_vb_v$ ，那么此时还是 $c_u \ge 0$ 作为合法条件。每次操作就是选择一堆石子，拿掉 $k$ ，再把 $k \times b_u$ 放到父亲堆里面。可以发现这对于刚刚说的结论没有任何影响，可以用一样的方法来做。唯一的例外在于，如果 $b_u = 0$ ，那么我们需要把这个点和父亲断开，然后会形成若干个独立的游戏，这个是 SG 函数的经典应用了。

复杂度 $O(n)$ 。