首页 > 代码库 > 计蒜客15430 XOR Queries(Trie处理位运算问题)

计蒜客15430 XOR Queries(Trie处理位运算问题)

题意:

给出一个长度为n的数组C,回答m个形式为(L, R, A, B)的询问,

含义为存在多少个不同的数组下标k属于[L, R]满足C[k] XOR A >= B(式中XOR为异或运算)。

T组测试数据.

每组第一行为两个整数n, m.(1 <= n, m <= 5e4).

第二行n个整数表示数组C.(0 <= C[i] <= 1e9).

接下来m行,第i行四个整数L[i], R[i], A[i], B[i](1 <= L[i] <= R[i] <= n, 0 <= A[i], B[i] <= 1e9.

对于每次询问,输出一个整数表示满足条件的数组下标数目。

分析:

对于一个区间[L,R],求满足C[k] xor A >= B的数目,那么怎么求呢?

我们可以对这段区间的每个数二进制化,然后从高位开始往低位,去建一个trie树,并计算出每个trie树的节点下面有多少个数,这样就可以通过A在trie树上移动得到最后结果,时间复杂度O(logn)

那么对于这样变化的区间,容易想到莫队,确实可以

不过有个更好的想法,就是ans[L,R]=ans[R]-ans[L-1],所以就是求前缀的答案就行了

也就是每次往trie树中插入一个数,然后去更新该位置有的答案(提前预处理出每个询问对应哪些个位置)

计蒜客15430 XOR Queries(Trie处理位运算问题)