Xor sum

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 200000
#define SQRSIZE 400
 
long long arr[MAXN]; // original array
long long block[SQRSIZE]; // decomposed array
long long block_size; // block size
 
void sqrt_decomposition_update(int index, long long value) {
    int block_number = index / block_size;
    block[block_number] ^= value - arr[index];
    arr[index] = value;
}
 
// Time Complexity : O(sqrt(n))
int sqrt_decomposition_query(int left, int right) {
    int sum = 0;
    while (left < right and left % block_size != 0 and left != 0) {
        sum ^= arr[left];
        left++;
    }
    while (left + block_size - 1 <= right) {
        sum ^= block[left / block_size];
        left += block_size;
    }
    while (left <= right) {
        sum ^= arr[left];
        left++;
    }
    return sum;
}
 
void sqrt_decomposition_preprocess(int input[], int n) {
    int block_index = -1;
    block_size = sqrt(n);
 
    for (int i = 0; i < n; i++) {
        arr[i] = input[i];
        if (i % block_size == 0)
            block_index++;
        block[block_index] ^= arr[i];
    }
}
 
int main() {
 
    int n, q;
    cin >> n >> q;
 
    int *input = new int[n];
    for (int i = 0; i < n; i++)
        cin >> input[i];
 
    sqrt_decomposition_preprocess(input, n);
 
    vector<long long> output;
 
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        long long o = sqrt_decomposition_query(a-1, b-1);
        output.push_back(o);
    }
 
    for (long long o : output)
        cout << o << endl;
 
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED