Description
已知一个长度为 (n) 的整数数列 (a_1,a_2,cdots,a_n) ,给定查询参数 (l,r) ,问在 ([l,r]) 区间内,有多少连续子序列满足异或和等于 (k) 。
CQOI 数据范围: (1leq nleq 10^5, a_i,kleq 10^5)
CF 数据范围: (1leq nleq 10^5, a_i,kleq 10^6)
Solution
撞题也是醉了...
莫队傻逼题,乱搞即可。
Code
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+5, SIZE = 1<<20;
int n, m, k, lim, a[N], cnt[SIZE]; ll ans[N];
struct tt {
int l, r, id;
bool operator < (const tt &b) const {
return l/lim == b.l/lim ? r < b.r : l < b.l;
}
}b[N];
void work() {
scanf("%d%d%d", &n, &m, &k); lim = sqrt(n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] ^= a[i-1];
for (int i = 1; i <= m; i++) scanf("%d%d", &b[i].l, &b[i].r), --b[i].l, b[i].id = i;
sort(b+1, b+m+1);
int curl = 1, curr = 0; ll sum = 0;
for (int i = 1; i <= m; i++) {
int l = b[i].l, r = b[i].r;
while (curr < r) sum += cnt[a[++curr]^k], ++cnt[a[curr]];
while (curl > l) sum += cnt[a[--curl]^k], ++cnt[a[curl]];
while (curr > r) --cnt[a[curr]], sum -= cnt[a[curr--]^k];
while (curl < l) --cnt[a[curl]], sum -= cnt[a[curl++]^k];
ans[b[i].id] = sum;
}
for (int i = 1; i <= m; i++) printf("%lld
", ans[i]);
}
int main() {work(); return 0; }