洛谷 P7003

考虑当左端点固定时，区间的 \(\&\) 和至多有 \(\log w\) 种，因为 \(1\) 的数量是单调不升的。

所以我们可以枚举区间左端点 \(i\)，然后 ST 表预处理区间 \(\&\) 和 + 二分求出一段 \(\&\) 和相同的区间。

然后设 \(pre_i\) 表示原序列的前缀异或和，那么设当前这段 \(\&\) 和相同的区间为 \(l,r\)，值为 \(x\)，那么就是要求 \(\sum_{j=l}^{r}[pre_j\oplus pre_{i-1}=x]\)，即 \(\sum_{j=l}^{r}[pre_j=pre_{i-1}\oplus x]\)，发现等式右边是个定值，那么就是求一段区间内一个数的出现次数，离散化后在 vector 里二分就好了。

时间复杂度 \(\mathcal O(n\log w\log n)\)。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005, M = 17;
int n;
int f[N][M], lg[N];
int pre[N], _[N], tot;
vector <int> pos[N];
ll ans;

int query(int l, int r) {
	int k = lg[r - l + 1];
	return f[l][k] & f[r - (1 << k) + 1][k];
}

int main() {
	scanf("%d", &n);
	lg[0] = -1;
	for (int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
	for (int i = 1; i <= n; ++i) scanf("%d", &f[i][0]), pre[i] = pre[i - 1] ^ f[i][0], _[++tot] = pre[i];
	sort(_ + 1, _ + tot + 1), tot = unique(_ + 1, _ + tot + 1) - (_ + 1);
	for (int i = 1; i <= n; ++i) pos[pre[i] = lower_bound(_ + 1, _ + tot + 1, pre[i]) - _].push_back(i);
	for (int j = 1; j <= lg[n]; ++j)
		for (int i = 1; i + (1 << j) - 1 <= n; ++i)
			f[i][j] = f[i][j - 1] & f[i + (1 << (j - 1))][j - 1];
	for (int i = 1; i <= n; ++i) {
		for (int l = i, r = i; l <= n; l = r + 1) {
			int L = l, R = n, val = query(i, l);
			while (L < R) {
				int mid = L + R + 1 >> 1;
				if (query(i, mid) != val) R = mid - 1;
				else L = mid;
			}
			r = L;
			val ^= _[pre[i - 1]];
			int p = lower_bound(_ + 1, _ + tot + 1, val) - _;
			if (p <= tot && _[p] == val)
				ans += upper_bound(pos[p].begin(), pos[p].end(), r) - lower_bound(pos[p].begin(), pos[p].end(), l);
		}
	}
	printf("%lld", ans);
	return 0;
}