CodeForces E. XOR and Favorite Number(Div.2)

题目链接：E. XOR and Favorite Number展开目录

题解展开目录

一个莫队的基础题，题目要求 [L,R] 里面有多少对子区间异或值为 k，记录一下前缀异或和 arr，因为 x^x=0，现在我们要求区间 [L,R] 的异或和值，用 arr 数组表示就是 arr [L-1]^arr [R]=k，或者说 arr [R]^k=arr [L-1]

import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    
    final static int N = 1 << 21;
    static long nowAns = 0;//当前答案
    static int n,m,k,block;
    static long[] cnt = new long[N];//每个数出现的次数
    static long[] ans = new long[N];//记录每个答案
    static int[] arr = new int[N];//前缀异或和
    static Query[] q = new Query[N];//询问
    
    public static class cmp implements Comparator<Query> {
        public int compare(Query x,Query y) {
            if(x.l / block == y.l / block)
                return x.r - y.r;
            return x.l / block - y.l / block;
        }
    }
        
    public static void remove(int x) {
        cnt[arr[x]]--;
        nowAns -= cnt[arr[x] ^ k];
    }

    public static void add(int x) {
        nowAns += cnt[arr[x] ^ k];
        cnt[arr[x]]++;
    }
    
    public static void main(String[] args) {
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int l = 1,r = 0;
        n = cin.nextInt();//数组长度
        m = cin.nextInt();//询问次数
        k = cin.nextInt();
        block = (int) Math.sqrt(n);//每块的大小
        for(int i = 1;i <= n;i++) {
            int tmp = cin.nextInt();
            arr[i] = arr[i - 1] ^ tmp;
        }
        for(int i = 1;i <= m;i++) {
            int tmp_l = cin.nextInt();
            int tmp_r = cin.nextInt();
            q[i] = new Query(tmp_l,tmp_r,i);//减1是为了将询问转换为下标
        }
        Arrays.sort(q,1,m + 1,new cmp());//sort是左闭右开的区间
        cnt[0] = 1;
        for(int i = 1;i <= m;i++) {
            while(l < q[i].l) {
                remove(l - 1);//移出数字
                l++;
            }
            while(l > q[i].l) {
                l--;
                add(l - 1);//加入数字
            }
            while(r < q[i].r) add(++r);//加入数字
            while(r > q[i].r) remove(r--);//移出数字
            ans[q[i].id] = nowAns;
        }
        for(int i = 1;i <= m;i++) System.out.println(ans[i]);
    }
}
class Query {
    int l,r,id;
    Query(int L,int R,int id) {
        this.l = L;
        this.r = R;
        this.id = id;
    }
}