牛客小白月赛30- I 区间异或

区间异或

题目描述：

有一个长度为 n 的数组 a[i] , 有 m 次询问， 每次询问给一个值 x ， 找出一个最短的区间， 使得这个区间的异或和 ≥ x , 输出区间长度。如果找不到输出 -1.

输入描述:

第一行两个整数 n , m (1 ≤ n ≤ 3000 and 0 ≤ m ≤ 2e5)
第二行 n 个整数 a[i] . (0≤ a[i] ≤ 1e9)
接下来 m 行， 每行一个整数 x , 代表一次询问。 (0 ≤ x ≤ 1e9)

输出描述:

每次询问输出满足条件的最短区间，如果找不到输出 -1

输入

5 3
16 5 2 8 32
4
48
33

输出

1
5
2
解题思路：
题中给出的数组范围是3000, 由这个信息中可以的来预处理出每个区间的最大值;然后从前往后取 max，得到一个非递减的数组。
每次查询在这个数组里面二分一个最小的位置，这个位置的值 大于等于x;
代码

for (int i = 1; i <= n; i ++ ) scanf ("%d", &a[i]), tl[i] = tl[i-1]^a[i];

    for (int l = 1; l <= n; l ++ )
        for (int r = l; r <= n; r ++ )
            dis[r - l + 1] = max(dis[r - l + 1], tl[r] ^ tl[l-1]);
    for (int i = 1; i <= n; i ++ ) dis[i] = max(dis[i], dis[i-1]);// 比前面小的直接覆盖，把dis数组变成非递减 
    for (int i = 1, x; i <= m; i ++ ){
        scanf ("%d", &x);
        int ans = lower_bound(dis + 1, dis + 1 + n, x) - dis;
        if (ans <= n) printf ("%d\n", ans);
        else printf ("-1\n");
    }