111

【模板】单调栈 处理每个点贡献的区间长度，差分一下即可

考虑对$a_i$建虚点，因为$2^{20} \approx 10^6$可以把不用的也建了。
注意到如果 $x \operatorname{and} y = y$ 且 $y \operatorname{and} z = z$，$x \operatorname{and} z = z$。
考虑对$x$和$x \operatorname{or} y \ (\ \operatorname{popcount}(y) = 1 \ \text{且} \ \operatorname{popcount}(x \operatorname{xor}\ (x \operatorname{or} y)))=1$的点建边。
虚点和真正的点连$w=0.5$的边。
注意$a_i$可能$\ =0$ 。

神秘计数，不会。

大佬用 min25 筛，我不会。 xz001有一个神秘的做法。
枚举较小的约数，贡献为$\gcd(x,y) = 1\ (x\le y \le n/x)$
考虑解$\gcd(x,y) = 1\ (y \le x)$
因为前$7$个质因数的乘积$\le 10^6$，分解质因数容斥即可。

类似字符串哈希，考虑在$\bmod\ p$意义下解方程。

注意到$m \le 2k \le 22 ,2^m \le 5\times 10^6$，爆搜即可。

【模板】manacher
没啥好说的，求完回文半径后就很简单了，二分就可以。

先建trie树转化为树上问题。 就转化成了p3354。 设$dp_{i,j,k,2}$表示点i用的按钮是j,i的子树内有k个按钮，i有/没有按钮的权值。 显然是一个树上背包。

开3个pq分别存每个点的3个值。 把目前的最大值pop出来 如果一个点有两个值相同，那么这个点就不能选，大标记删除。 找到第一个没被标记的点对就是答案。