考虑当左端点固定时,区间的 \(\&\) 和至多有 \(\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;
}
标签:pre,洛谷,log,val,int,P7003,mid,区间
From: https://www.cnblogs.com/Kobe303/p/16829789.html