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)$。