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]
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)).
/*=================================*\
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;
}
