310

0310测试

T1

树上单点修改，查一个点和所有祖先权值异或的最大值。

首先想到树剖，然后树剖每个节点都要维护 Trie，修改 $O(\log^2 n)$，查询 $O(\log^3 n)$，时间是 $O(n\log^3n)$ 的，空间是 $O(n\log^2n)$ 的，过不了。

然后它要查的是祖先，考虑直接用 dfs 序，然后变成了区间修改单点查询，时间复杂度降到了 $O(n\log ^2)$。空间还是过不了。

这个时候我想到可以根号重构，处理树的复杂度是 $O(n\log n)$，暴力询问是 $O(n)$，所以每 $\sqrt {n\log n}$ 个询问分块处理。

根号重构复杂度高了被卡了常。

实际上我们注意到 dfs 序那个询问是可以拆分的，把每个线段树节点的所有修改和询问离线下来做就可以了。

另外就是 Trie 可以写循环版本的，常数低很多。

T2

先考虑给一个数怎么算贡献，如果它只有一个二进制位为 $1$，那么简单积分一下就知道答案是 $2$。因为最后只会剩下最高位，所以考虑一个低位的贡献，显然它的贡献就是它为 $1$ 的概率，记作 $a$。

然后可以记录一下前一个 $a$，如果当前位是初始 $0$，那么它是 $1$ 的概率为 $\frac{a}{2}$，否则为 $1-\frac{a}{2}$。

此时有两种思路，其一是对 $a$ 的和进行数位 DP，其二是考虑每一对二进制位的贡献。

由于每一个二进制位对当前二进制位的贡献是可以拆分的，所以也就很容易了。

我用了第二种思路。

教训

• 数位 DP 时 long long 级别的数要取模，特别是 1ll<<x！一定要先取模再算乘法！

• __builtin_clz,__builtin_ctz 在 $x=0$ 时没定义，数位 DP 时最好把 $0$ 先判了再做。

T3

暴力挂了。

原因是轮廓线状压换行的时候清空没有清干净。

for(int mask=0;mask<p3[n];mask++){
    g[0][mask]=min(min(g[0][mask],g[1][mask]),g[2][mask]); // 转移到下一行
    g[1][mask]=g[2][mask]=1e9; //清空上一行的无用信息，这句没加
}