XOR Related problem

Revision en1, by adarsh000321, 2021-05-15 17:22:24

Note: This problem has been asked in one of the online coding challenges.

Given an array A of size N. You are asked Q queries. There will be two types of queries:

1 L R K: Print “Yes” if the subarray A[L, R] can be split into K contiguous subarrays such that each of these K subarrays have a subarray XOR with odd number od set bits. Otherwise, print “No”.

2 L X: Update A[L] = X .

Constraints: 1 <= A[i] <= 1e9 1 <= L, R, K <= N 1 <= N, Q <= 1e5

Can anyone give me some idea about how to solve this problem?

Tags #xor, # dp, #bit

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English adarsh000321 2021-05-15 17:22:24 605 Initial revision (published)