1080 毒瘤xor - 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge

1080: 毒瘤xor

时间限制：1.000s

内存限制：128MB

提交通过: 2 提交: 2 统计

小a有N个数a₁, a₂, ..., a_N，给出q个询问，每次询问给出区间[L, R]，现在请你找到一个数X，使得
1、$0 \leq X \leq 2^{31}$
2、$\displaystyle \sum_{i=L}^R{X⊕a_i}$ 最大，⊕表示异或操作

第一行一个整数N，表示序列的长度
第二行N个整数，表示序列内的元素
第三行一个整数q，表示询问的个数
接下来q行，每行两个整数[L, R]，表示询问的区间

备注：
对于30%的数据，n , q ≤ 10
对于60%的数据，n , q ≤ 1000

对于100%的数据，n, q ≤ 10⁵

保证a_i < 2³¹

输出q行，每行一个整数表示答案
若有多组可行解，请输出较小的解

5 
4 78 12 1 3
3
2 5
1 4
3 3

2147483632
2147483635
2147483635

位运算贪心前缀和

提交