суммирование XOR X с каждым из элементов массива от диапазона L до R оба - PullRequest
Новая
       93

суммирование XOR X с каждым из элементов массива от диапазона L до R оба

0 голосов
/ 17 ноября 2018

Я пытаюсь решить эту проблему Я требую пробный бой в hackerearth, и я в основном решаю, но я получаю TLE в тестовом сценарии после 3 Мои решения требуют времени

O (Q * R + L-1), что означает O (N ^ 2) Есть ли способ решить эту проблему В O (N) или меньше времени Вот мое решение 

#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);
}
}

Проблема:

Вам дан массив целых чисел A размера N. Теперь вам дано Q запросов для выполнения над этим массивом.

В каждом запросе вы получаете 3 целых числа, разделенных пробелами L, R и X, вам необходимо вывести суммирование XOR для X с каждым элементом массива из диапазона от L до R, включая оба (индексация на основе 1) ). 

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

Ограничения:

1 <= N, Q <= 10 ^ 5 </p>

1 <= A [i] <= 10 ^ 9 </p>

1 <= L, R <= N </p>

1 <= X <= 10 ^ 9 </p>

1 Ответ

0 голосов
/ 17 ноября 2018

Мы можем хранить частоту каждого бита в своем собственном префиксном массиве.Для каждого установленного бита в X у нас столько раз, сколько в этом диапазоне нулевых битов.Для каждого неустановленного бита в 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).

...