TJOI2018 异或

树上问题，容易想到可以 dfs 序和树链剖分，考虑如何维护权值。

其实就是需要给任意段进行一个 01-trie 树，那么直接可持久化就行了，时间复杂度为 $O(q\log ^2n)$。

CF241B Friends

考虑二分第 $m$ 大的数是什么，然后找到之后统计就行了。

有些细节需要注意，首先需要按位统计所以空间是 $\log^2$ 的，于是要用 unsigned short 卡空间。

其次是第 $m$ 的大数可能有很多，所以最后需要特判一下。

最后就是 $2m>2^{31}-1$，$10^9\oplus10^9>2^{31}-1$，需要多开 long long 比较恶心。

时间复杂度为 $O(n\log^2 V)$ 。

CF960H Santa's Gift

题目复杂不可读，固抄了一个形式化题意。

给定一个 $n$ 个节点的有根树，有 $m$ 中颜色，第 $i$ 个点的颜色为 $f_i$，颜色 $i$ 的权值为 $c_i$。

有两种操作：

1. 将 $f_x\gets y$。
2. 从树中等概率的选择一个节点 $i$，求解 $(S_i\times c_x-C)^2$ 的期望，其中 $S_i$ 表示以 $i$ 为根的子树中 $x$ 颜色的数量。

显然 $\dfrac{1}{n}\sum\limits_{i=1}^n (S_i\times c_x-C)^2$ 这个东西是很难直接维护的，那么拆开得到：

$\begin{aligned} \dfrac{1}{n}\sum\limits_{i=1}^n (S_i\times c_x-C)^2&=\dfrac{1}{n}\left( \sum\limits_{i=1}^n (S_i\times c_x)^2-2C\times c_x\times S_i+C^2 \right)\\ &=C^2+\dfrac{{c_{x}}^2}{n}\sum\limits_{i=1}^n {S_i}^2-\dfrac{2C\times c_{x}}{n}\sum\limits S_{i} \end{aligned}$

所以现在就只需要维护 $\sum\limits_{i=1}^n {S_{i}}^2$ 和 $\sum\limits_{i=1}^n S_{i}$ 就可以了。

如果改变了点 $x$，那么其原本到根路径上 $S_{i}$ 所有的 $x$ 都要减 $1$。

$\begin{aligned} (S_{i}-1)^2={S_{i}}^2-2\times S_{i}+1 \end{aligned}$

但是因为直接开 $m$ 棵线段树的空间复杂度为 $O(nm)$，所以需要动态开点做到 $O(m\log n)$。

时间复杂度为 $O(n\max\{f_{i}\}+q\log n)$。

CF407E k-d-sequence

首先特判 $d=0$ 的情况，然后继续分析。

考虑如何确定一个区间是否合法：

• 满足这个区间没有重复的数。
• 这个区间所有的数都关于 $d$ 同余。
• $\dfrac{\max-\min}{d}+l-r\le k$。

套路的考虑枚举有端点，计算 $l$ 的最小值。

对于第一个要求直接开一个桶就行了，对于第二个要求也可以直接维护出来，比较有难度的其实是如何维护第 $3$ 个要求。

因为 $r$ 是固定的，我们把 $r$ 移过去得到：

$\begin{aligned} \dfrac{\max-\min}{d} +l\le k+r \end{aligned}$

因为除 $d$ 很难维护，不妨整体乘上去，得到：

$\begin{aligned} \max-\min +l\times d\le d\times (k+r) \end{aligned}$

考虑写一个扫描线，显然对于 $l+d$ 直接在线段树里赋值就行了。

对于 $\min$ 和 $\max$ 的处理也是比较套路的。

考虑维护两个单调栈，那么如果 $r\gets r+1$ 时就把 $a_{r}$ 加入栈中，把栈中从上到小数第二个元素（第一个是 $a_{r}$）到 $r$ 的 $\min$ 和 $\max$ 都分别改了就行了。

处理之后直接在线段树上二分找最小的 $l$ 就行了。

这里有一些细节，笔者写的时候脑子是瓦特的所以没有注意。

首先，不需要维护 $\min$ 和 $\max$ 的具体值的，直接区间加或者区间减就行了。

其次，对于线段树上二分被 $1,2$ 限制所拒绝的点直接赋 $inf$ 就行了，因为这个位置显然是单调的。

最后，不建树可以跑到第 $11$ 个点，别问笔者怎么知道的。

时间复杂度为 $O(n\log n)$。