题目链接:http://codeforces.com/problemset/problem/617/E

题目:

  给你a a a ··· a 个数,m次询问:在[L, R] 里面又多少中 [l, r] 使得 a xor a xor ··· a 为 k。

题解:

  本题只有区间查询没有区间修改,而且数据量不大(10w),所以可以用离线的方法解决。

  使用莫队算法来解决,就需要O(1)的修改[L, R+1] 、[L, R-1]、[L+1, R]、[L-1, R]。

  详细的莫队可以百度学一下。

  这里讲一下怎么样通过O(1)来修改

  1)我们需要求前缀xor。

  2)[L, R] -> [L, R+1]:这里添加了一个a , 就可以通过前缀xor T,所以我们需要找 T ^ k  H 的个数(因为H^T=K-> H=T^K)。

      如果H在前面出现过,比如(全部是前缀xor)1 2 1[加入]。这时xor 为1 ,我们当k为0, 那么 0^1 = 1的个数就为1。

      这里的1的数量有什么意义。如果我们要想 1 [2 1] 这一段的xor ,是不是应该  T(1)xor T(1) = 0 = k;

    [L, R] -> [L, R-1] : 这里是删除了一个a, num[T] --, 我们要求的是 k^ T 的个数 。

      1 2 1 1[删除], k = 0, 0^1 = 1 , 这个有2个1。这里2个的意思 1 [2 1 1] ( T xor T = 0)和 1 2 1 [1]  (T xor T = 0),因为删去了a 所以a 结尾的区间就要减去。

    [L, R] -> [L-1, R] : 这个是增加多一个 a  。就是在[L-1, R] 这个里面找 [L-1, r(r<R)] 使得xor 为k , 所以就需要 k^((L-1)-1)。

    [L, R] -> [L+1, R] :这里是删除了 a 。就是在 [L, r(r<R)] 找 xor 为 k 的 。T[r]^T[L-1] = k。

      num[0] = 1 。这里是应为一开始前缀异或为0 .

 

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
using namespace std;
typedef long long LL;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
const int INF = 0x7fffffff;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+;
const int maxn = +;
int a[maxn];
LL num[];
LL x[maxn];
LL ans[maxn];
struct Point
{
int l, r, id;
}node[maxn];
int unit, n, m, k;
void init() {
ms(a, );
ms(ans, );
ms(num, );
ms(x, );
}
bool cmp(Point x1, Point x2)
{
if(x1.l/unit != x2.l/unit){
return x1.l/unit < x2.l/unit;
}
else
return x1.r < x2.r;
}
void work()
{
for(int i = ;i<=n;i++)
x[i] = x[i-]^a[i]; int L, R;
LL temp = ;
L = , R = ;
num[]++;
for(int i = ;i<m;i++){
while(R<node[i].r){
R++;
temp+=num[k^x[R]];
num[x[R]]++;
}
while(R>node[i].r){
num[x[R]]--;
temp-=num[x[R]^k];
R--;
}
while(L>node[i].l){
L--;
temp+=num[k^x[L-]];
num[x[L-]]++;
}
while(L<node[i].l){
num[x[L-]]--;
temp-=num[x[L-]^k];
L++;
}
ans[node[i].id] = temp;
}
}
void solve() {
scanf("%d%d%d", &n, &m, &k);
unit = (int)sqrt(n);
for(int i = ;i<=n;i++) scanf("%d", &a[i]);
for(int i = ;i<m;i++){
node[i].id = i;
scanf("%d%d", &node[i].l, &node[i].r);
}
sort(node, node+m, cmp);
work();
for(int i = ;i<m;i++){
printf("%lld\n", ans[i]);
}
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
// ios::sync_with_stdio(0);
// cin.tie(0); init();
solve(); return ;
}
05-27 10:36