2025.11.18 ds专项……？

考虑一只鞋子肯定是找与它最近的另一侧鞋子匹配。然后可以固定鞋子的方向，比如从右往左，右边的鞋子找左边的鞋子。这样肯定是不劣的。

先按大小和左右记录鞋子的位置，然后从右往左扫，和最近的能匹配的鞋子匹配，此时需要去除这两个位置中间已经匹配过的鞋子，将未匹配设为 1，匹配设为 0，然后就可以用 BIT 快速计算了。时间复杂度 $O(n \log n)$。

首先注意到：温度升高时，冰系的能量总和会升高，火系的能量总和会降低，而温度确定时，总能量为冰系能量综合与火系能量总和的最小值的两倍。因此，温度升高时，总能量先升高再降低。

考虑离散化温度，分别开两个 BIT 维护冰系和火系的以温度为下标的前缀和，那么利用 BIT 找出冰系大于火系时的最大能量，与火系大于冰系的最大能量，就可以得到答案。

考虑二分，复杂度 $O(n \log^2 n)$，期望 60pts。使用 BIT 倍增的 trick，优化到 $O(n \log n)$，可以通过本题。

板板题。

注意到异或可差分，令 $s_x$ 为 $1$ 到 $x$ 的边权异或和，则树上两个点 $x,y$ 的异或路径为 $s_x \oplus s_y$。问题转化为求一个序列中取两个数的异或最大值。把每个 $s_x$ 丢进 01trie 里维护，按位查询即可。时间复杂度 $O(n \log V)$。