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;}
}