【题解】CF1438E Yurii Can Do Everything

CF1438E Yurii Can Do Everything

给定一个长度为 $n$ 的数组 $a$，求长度至少为 $3$，且满足 $a_l\oplus a_r=\sum_{i=l+1}^{r-1} a_i$ 的子区间 $[l,r]$ 的数量，其中 $\oplus$ 是异或。
$3\le n\le 2\times 10^5,1\le a_i< 2^{30}$。

$\texttt{Solution}$

vp的时候随便扯了一个算法竟然碰上了？？？

考虑最 $\text{naive}$ 的暴力，直接 $\mathcal{O}(n^2)$ 判断是很简单的。

优化一下，不难发现如果我们令 $a_i$ 的二进制最高位为 $2^{k_i}$，那么 $a_i\oplus a_j<2^{\max(k_i,k_j)+1}$。所以当我们确定一个左端点 $l$，枚举右端点时，当中间的和 $\ge 2^{k_l+1}$ 的时候我们就不继续枚举了。

然后正着反着各做一遍再判重即可，因为上面超过 $2^{k_l+1}$ 就不枚举了，但实际上是超过 $2^{\max(k_l,k_r)+1}$ 才跳出，正反各做一遍才能取到这个区间两边 $k$ 的 $\max$。

考虑证明复杂度：

现在只考虑正过来做的情况。对于一个 $a_r$，他会被多少个 $l$ 遍历到？可以得到：

对于每一种取值不同的 $k_l$，$a_r$ 至多被遍历 $2$ 次。

假设我们有超过 $2$ 个取值为 $k_l$ 的位置会遍历到 $a_r$，假设他们为 $l_1<l_2<l_3$。那么区间 $[l_1,r]$ 中，有 $k_{l_2}=k_{l_3}=k_{l_1}$，因此 $a_{l_2}+a_{l_3}\ge 2^{k_{l_1}+1}$，与上述做法不符。

因此每一个位置，都只会被遍历 $\mathcal{O}(\log a)$ 次。

所以时间复杂度是 $\mathcal{O}(n\log a)$。