Izračunavanje XOR-a za date podnizove

Data je lista arr pozitivnih celih brojeva. Takođe, data je lista upita, gde svaki upit ima oblik [$left_i$,$right_i$]. Za svaki upit, izračunajte XOR elemenata u listi od indeksa $left_i$ do indeksa $right_i$, uključujući oba indeksa. Drugim rečima, za svaki upit, izračunajte XOR podniza od arr[$left_i$] do arr[$right_i$] (uključujući oba indeksa).

Vratićete listu answer, gde je answer[i] rezultat i-tog upita.

Ulaz

Dva broja n i m. Prvi broj n predstavlja veličinu niza arr, dok drugi broj m predstavlja veličinu niza queries
Lista arr koja sadrži pozitivne cele brojeve: arr[0], arr[1], ..., arr[n-1].
Lista queries, gde je svaki element par koji predstavlja indekse podniza za koji treba da se izračuna XOR.
$0 \leq left_i \le right_i \le n$. U slučaju da je $left_i == right_i$, potrebno je vratiti samo element niza na poziciji arr[$left_i$]

Izlaz

Lista answer celih brojeva, gde je answer[i] rezultat XOR operacije za podniz definisan u i-tom upitu.

Primer 1

Ulaz

Izlaz

1 15 6

Primer 2

Ulaz

Izlaz

2 7 14 8

Rešenje

`main.c`

#include <stdio.h>
#include <stdlib.h>

void xor_podnizova(int* arr, int arr_size, int** queries, int queries_size, int* result){
	// rešenje zasnovano na prefiksnim nizovima
	int* prefixXOR = (int*)malloc((arr_size + 1) * sizeof(int));
	prefixXOR[0] = 0;  // prvi element je 0 jer XOR od praznog niza je 0 jer je to neutral
	for (int i = 0; i < arr_size; i++) {
        prefixXOR[i + 1] = prefixXOR[i] ^ arr[i]; 
    }


	for (int i = 0; i < queries_size; i++) {
        int left = queries[i][0];
        int right = queries[i][1];
        
        // XOR za interval [left, right] je prefixXOR[right + 1] ^ prefixXOR[left].
        result[i] = prefixXOR[right + 1] ^ prefixXOR[left];
    }

    free(prefixXOR);
}


int main(void)
{
	int n, m;
	scanf("%d", &n); 
	scanf("%d", &m); 
    
	int* arr = (int*)malloc(n * sizeof(int));
	for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]); 
    }

	int** queries = (int**)malloc(m * sizeof(int*));
	for (int i = 0; i < m; i++) {
        queries[i] = (int*)malloc(2 * sizeof(int));
        scanf("%d %d", &queries[i][0], &queries[i][1]); 
    }

	int* answer = (int*)malloc(m * sizeof(int));

	xor_podnizova(arr, n, queries, m, answer);

	for (int i = 0; i < m; i++) {
        printf("%d ", answer[i]);
    }
    printf("\n");


	free(arr);
    for (int i = 0; i < m; i++) {
        free(queries[i]);
    }
    free(queries);
    free(answer);

	return 0;
}