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

题目：

　　给你a₁ a₂ a₃ ··· a_n 个数，m次询问：在[L, R] 里面又多少中 [l, r] 使得 a_l xor a_l+1 xor ··· a_r 为 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_R+1 , 就可以通过前缀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_R， num[T_aR] --，我们要求的是 k^ T_aR 的个数。

　　　　　　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_R 所以a_R 结尾的区间就要减去。

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

　　　　[L, R] -> [L+1, R] ：这里是删除了 a_L 。就是在 [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 ;

 }

巴特西

codeforces 617 E. XOR and Favorite Number（莫队算法）

题目：

题解：

最新文章

热门文章