题目描述

给定一个长度为 n 的数列 A₁, A₂, · · · , A_n 和一个非负整数 x，给定 m 次查询, 每次询问能否从某个区间 [l,r] 中选择两个数使得他们的异或等于 x 。

输入格式

输入的第一行包含三个整数 n, m, x 。

第二行包含 n 个整数 A₁, A₂, · · · , A_n 。

接下来 m 行，每行包含两个整数 l_i ,r_i 表示询问区间 [l_i ,r_i ] 。

输出格式

对于每个询问, 如果该区间内存在两个数的异或为 x 则输出 yes, 否则输出 no。

样例输入

复制

4 4 1
1 2 3 4
1 4
1 2
2 3
3 3

样例输出

yes
no
yes
no

提示

显然整个数列中只有 2, 3 的异或为 1。

对于 20% 的评测用例，1 ≤ n, m ≤ 100；

对于 40% 的评测用例，1 ≤ n, m ≤ 1000；

对于所有评测用例，1 ≤ n, m ≤ 100000 ，0 ≤ x < 2²⁰ ，1 ≤ l_i ≤ r_i ≤ n ， 0 ≤ A_i < 2²⁰。 

代码：

import java.util.Scanner;

public class 选数异或1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int x = in.nextInt();
        int[] map = new int[1<<20];
        long[] dp = new long[n+1];
        for (int i =1;i<n+1;i++){
            int a = in.nextInt();
            dp[i] = Math.max(dp[i-1],map[a^x]);
            map[a] = i;
        }
        /*
        输入4 4 1
            1 4 3 2
            1 4
            1 2
            2 3
            3 3
            dp[1]= 0 map[1] =1
            dp[2]= 0 map[4] =2
            dp[3]=0  map[3] =3
            dp[4]=3  map[2] =4
            输出结果就第一组数据输出yes，看到这一行：dp[4]=3  map[2] =4  dp[i]的数字，是数组的索引，map[a] map里的是数组的数字，它里面记录的
            是该数字所在的位置
            然后我们看到这一行：dp[r]>=l，他是通过dp[r]去找，此时我们带入数字，dp[4]>1,那上面的数组中可以看到dp[4]=3，为什么？因为我们的异或是
            1，那1^2=3,想要的到结果是异或1，那就要2^3,我们可以发现，前面就有3的位置，然后我们可以发现map[3]=3，3的位置就在第三个索引，然后我们在跳到
            dp[4]>=1==3>=1，那条件成立，他需要的值是3，正好在1-3这个范围，所以输出yes,如果3不在这个范围，那只能输出no了


                     */
        while (m -->0){
            int l = in.nextInt();
            int r = in.nextInt();
            if (dp[r]>=l){
                System.out.println("yes");
            }else {
                System.out.println("no");
            }
        }
    }
}