↵
↵
<spoiler summary="Statement">↵
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$.↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Greedy.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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?↵
↵
<spoiler summary="Answer">↵
Yes. You could easily prove that.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Have you found some cases that the solution in Hint 2 dosen't work?↵
↵
Try to reverse the array.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
**UPD** Thanks to [user:nonrice,2024-06-06] and [user:sammyuri,2024-06-06], I fix the solution.↵
↵
<spoiler summary="Statement">↵
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$.↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Greedy.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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?↵
↵
<spoiler summary="Answer">↵
Yes. You could easily prove that.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Have you found some cases that the solution in Hint 2 dosen't work?↵
↵
Try to reverse the array.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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.↵
</spoiler>↵
↵
**UPD** Thanks to [user:nonrice,2024-06-06] and [user:sammyuri,2024-06-06], I fix the solution.↵
