Unofficial Editorial of problem CHEFEXQ from codechef december 2017 long contest

Problem link: CHEFEXQ

Given an array of n elements and q queries of 2 types:

• type 1: Given two numbers p and x, the value at index p should be updated to x.
• type 2: Given two numbers p and x, calculate total number of subarrays whose starting index is 0 and the last index is ≤ p and the xor of all elements in that subarray is equal to x.

Solution:

This problem can be solved using square root decomposition technique.

Let the given array is arr[] Let take another array called xorr[] to store the cumulative xor value, where xorr[i] is equal to xor value of all element from index 0 to i, i.e. : xorr[i] = arr[0] ^ arr1 ^ ......... arr[n-1],
i.e. xorr[0] = arr[0], and for 1<= i <= n-1, xorr[i] = xorr[i-1] ^ arr[i]

Now the problem can be converted to: You are given array xorr[] of size n and there are q queries of the 2 types:

• type 1: Given two numbers p and x . Let y = arr[p] ^ x. For each index i from p to n-1 perform xorr[i] = xorr[i] ^ y .
• type 2: Given two numbers p and x. Calculate how many number in array xorr[] from index 0 to p, which are equals to x.

We will split the array into several blocks, size of each block will sqrt(n). Let blocksize = sqrt(n). Here,

[0, blocksize-1] is the first block,

[blocksize, 2 * blocksize-1] is the second block,

i.e. [(i-1)*blocksize, i * block_size - 1] is the i'th block.

Notice that starting index of every block is divisible by blocksize. For any index i the block number is i/blocksize.

Now, let cnt[blocksize][MAX] be another array to count the frequency of numbers in each block. cnt[i][j] will denotes how many numbers equal to j in the block number i.

For the first type of query i.e. update:

For each index i from p to n-1 until we get such index i which is divisible by blocksize, i.e. such i which is a starting index of any block, we decrease the frequency of xorr[i] by 1, i.e. cnt[i/blocksize][xorr[i]]--; then set xorr[i] = xorr[i] ^ y and increase the frequency of xorr[i] by 1, i.e. cnt[i/blocksize][xorr[i]]++;

For rest of the index i, i.e. such index i where i is the starting index of any block, we will do a lazy operation for that block starting at index i.

Let take another array called lazy[] of size blocksize. If lazy[i] = x, it denotes that each element in block i will be xorred by x. Initially lazy[] value for each block is 0.

Now, for rest of the lazy update operation, will change the lazy[j] value for each block j which are at right side of index i, as lazy[j] = lazy[j] ^ y.

For query of the 2nd type:

Let initialize ans = 0;

From index 0 to p, for the indices which are in a full block, to calculate the frequency of number x, in block i, we actually have to calculate the frequency of the number x^lazy[i], since the elements in block i is to be xorred with lazy[i], instead of xorring each element we will find the numbers x^lazy[i]. Because the numbers which are equals to x^lazy[i], they will be equals to x after xorring with lazy[i].

So add the frequency to our ans: ans = ans + cnt[i][x^lazy[i]], for each full block i which are left side of index p.

For the only partial block(if any), left side of index p, just iterate each index j and if xorr[j] = lazy[i]^x, (where i is the block number for index j, i.e. i = j/blocksize) then add 1 to our ans, i.e. ans = ans + 1.

Finally, just print the ans.

Overall time and memory complexity will be: O(q.sqrt(n)).

Code:

Here is my submission link: my AC submission

/*=================================*\

      Md. Shahidul Islam
         CSE, BRUR
      Rangpur, Bangladesh
 mail: shahidul.cse.brur@gmail.com
 FB  : fb.com/shahidul.brur
 Blog: shahidul-brur.blogspot.com(in Bengali),
       shahidul-brur-en.blogspot.com(in English)
\*=================================*/
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000002;
const int N = 100002;

int arr[N], blk_sz, n, cnt[320][MAX];
int lazy[350], xorr[N];

void update(int idx, int rep)
{
    for (; idx<n && idx%blk_sz != 0; idx++){
        cnt[idx/blk_sz][xorr[idx]]--;
        xorr[idx] ^= rep;
        cnt[idx/blk_sz][xorr[idx]]++;
    }
    
    for(;idx<n;idx+=blk_sz){
        lazy[idx/blk_sz]^=rep;
    }
}

int query(int idx, int k)
{
    int sum = 0, cur;
    for(cur = 0; (cur+1)*blk_sz-1<=idx; cur++){
        int val = k^lazy[cur];
        sum+=cnt[cur][val];
    }
    
    for(int i = cur*blk_sz;i<=idx;i++){
        if ((xorr[i]^lazy[cur]) == k)
            sum++;
    }
    return sum;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q, i;
    cin>>n>>q;
    blk_sz = sqrt(n);
    cin>>arr[0];
    xorr[0] = arr[0];
    cnt[0][xorr[0]]++;
    for(i=1;i<n;i++){
        cin>>arr[i];
        xorr[i] = xorr[i-1]^arr[i];
        cnt[i/blk_sz][xorr[i]]++;
    }
    
    while(q--){
        int tp, idx, x;
        cin>>tp>>idx>>x;
        --idx;
        
        if(tp==1){
            int rep = arr[idx]^x;
            update(idx, rep);
            arr[idx] = x;
        }
        else {
            int ans = query(idx, x);
            cout << ans << "\n";
        }
    }
    return 0;
}

Read More