c - X 与范围 L 到 R 中的每个数组元素的 XOR 的总和

Question

我正在努力解决这个问题i demand a trial by combat在 hackerearth 中，我主要解决了问题，但在 3 之后我在测试用例中得到了 TLE 我的解决方案需要时间复杂度

O(Q*R+L-1) which mean O(N^2) Is there any way to solve this problem In O(N) or less time Here is my solution

#include <stdio.h>
#include <stdlib.h>
#define ll long long 

int main(){

ll q,x,n,r,l;

scanf("%lld %lld",&n,&q);

ll arr[n];

for(ll i=0; i<n; i++){

    scanf("%lld",&arr[i]);
}

while(q--){

    scanf("%lld %lld %lld",&l,&r,&x);

    ll sum = 0;

    for(ll i=l-1; i<r; i++){

        sum += arr[i]^x;
    }

    printf("%lld\n",sum);
}
}

问题:

给定一个大小为 N 的整数数组 A。现在给定要对该数组执行的 Q 个查询。

在每个查询中，给定 3 个空格分隔的整数 L、R 和 X，您需要输出 X 与范围 L 到 R 范围内的每个数组元素的 XOR 的总和(包括(基于 1 的索引) ).

sum (i=l to r) of A[i] XOR X     In simple terms

约束:

1 <= N,Q <= 10^5

1 <= A[i] <= 10^9

1 <= L,R <= N

1 <= X <= 10^9

Answer 1

我们可以将每个位的频率存储在它自己的前缀数组中。对于 X 中的每个设置位，我们有与该范围内的零位一样多的 1。对于 X 中每个未设置的位，我们有与该范围内的位一样多的位。

例如:

A = [3, 4]

// Frequency prefixes of each bit
ps[0] = [1, 1]
ps[1] = [1, 1]
ps[2] = [0, 1]

X = 5, L = 1, R = 2

bit 0 is set in X so we add one 1
  (for the unset bit 0 in 4)

bit 1 is unset in X so we add one 1
  (for the set bit 1 in 3)

bit 2 is set in X so we add one 1
  (for the unset bit in 3)

1*1 + 1*2 + 1*4 = 7

对于每个查询，我们可以使用我们的位频率前缀数组在 O(1) 的范围内获得每个位的数量。然后我们需要对 30 次乘法求和。总共 30 * 10^5 个查询，即 O(Q)。