本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-27 20:04:01
题解思路：
我们会发现一个性质：满足条件的区间不会很多。
因为满足条件的数很少，所以我们就可以用暴力。
我们先假设，这个区间是以 $a_l$ 为主导的，就是 $a_l$ 是 $a_l$ 和 $a_r$ 里二进制最高的一位。
对于这样的情况下，那么我们就暴力求满足条件的区间就可以了。
先对于 $l$ 枚举 $r$。
终止条件是什么呢？
我们假设最高位是第 k 位，那么 $\sum^{n}_{i = 1}a_i$ 一定要 $\le 2^{k + 1}$，首先我们最大值在第 k 位上，而异或又是不进位加法，所以这个区间的和就是一定要 $\le 2^{k + 1}$ 的。
所以我们就暴力枚举 $r$，当遇到不符合这个条件的 $r$ 时，就终止就可以了。
然后再倒着，对于 $r$ 枚举 $l$，就可以了。
证明时间复杂度：
假设这是以第 $k$ 位二进制，那么最多有 $\log n$ 位二进制。对于每个二进制的情况下呢，我们去讨论。
我们假设二进制最高位为 $k$，的下标有： $p_1 , p_2 ... ... p_n$，假设 $l = p_1$，那么当 $r = p_3$ 时一定会终止，因为要是 $l = p_1 , r = p_3$ 时，累加和就是：$p_2 + p_3$ 而这个数一定会超过 $2^{k + 1}$。
那么对于每个下标累加和是多少： $\sum^{x}{i = 3} p_i - p{i - 2}$
那么这些数的累加和算下来他就是 $p_x + p_{x - 1} - p_1 - p_2 \le 2n$，就是一个 $O(n)$ 级别的。
有 $\log n$ 次操作，，每次 $O(n)$ 总时间复杂度为 $O(n \log n)$
AC CODE:
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
#include <set>
using namespace std;
typedef long long ll;
const int N = 200010;
int n;
int a[N];
set <pair <int , int>> s;\/\/用set去重
int log2 (int x) {\/\/求log2
int cnt = 0;
while (x) {
++ cnt;
x >>= 1;
}
return cnt;
}
void solve (bool op) {\/\/0代表正着，1代表倒着
vector <int> pre (n + 10);
for (int i = 1; i <= n; ++ i)
pre[i] = pre[i - 1] + a[i];\/\/求前缀和
for (int i = 1; i <= n - 2; ++ i) {
ll sum = a[i + 1];
int x = log2 (a[i]) + 1;
for (int j = i + 2; j <= n; ++ j) {
if ((a[i] ^ a[j]) == pre[j - 1] - pre[i]) {\/\/看看这个区间是否满足这个性质
if (!op) s.insert ({i , j});\/\/正着直接插入
else s.insert ({n - j + 1 , n - i + 1});\/\/倒着
}
if ((sum + a[i]) > (1ll << x)) break;\/\/超过了范围，break
sum += a[j];
}
}
}
int main() {
scanf ("%d" , &n);
for (int i = 1; i <= n; ++ i)
scanf ("%d" , &a[i]);
solve (0);\/\/正着来
reverse (a + 1, a + 1 + n);
solve (1);\/\/倒着来
printf ("%d\n" , (int)s.size());\/\/输出答案
return 0;
}
码字不易，求赞！
从最上边的点，到最后一个点，边权是： $(w_1 + w_2)^2$
鲁ICP备2025150228号