You are given an array $$$a_1,a_2,\ldots,a_n \; (1 \le n \le 10^5,0 \le a_i \le 10^9)$$$ and two integers $$$k,x$$$, determine if it is possible to divide the array into exactly $$$k$$$ segments $$$[l_1,r_1],[l_2,r_2],\ldots,[l_k,r_k] \; (l_1 = 1,r_k = n,l_{i+1} = r_i + 1)$$$ such that $$$\forall i \in [1,k], \oplus_{j=l_i}^{r_i} a_j \le x$$$.
Greedy.
Consider the first segment. Let $$$p$$$ be the mininum position such that $$$\oplus_{j=1}^p a_j \le x$$$, is the partition $$$[l_1,r_1] = [1,p]$$$ optimal?
Yes. You could easily prove that.
Have you found some cases that the solution in Hint 2 dosen't work?
Try to reverse the array.
Read the hints first.
For each segment, we want it to be as short as possible. Thus, we can just iterate $$$r$$$ from $$$l$$$ to $$$n$$$, when the XOR sum of $$$a[l,r]$$$ is not greater than $$$x$$$, divide here. If we get exactly $$$k$$$ segments, output Yes
, otherwise the answer is No
.
There's a small case: sometimes you need to reverse the array and calculate again, think about why.