P4563 [JXOI2018] Guards

Jiutiao Kelian is a girl who loves sports.

On this day she goes mountain climbing. For her safety, her father hires some bodyguards to stay fixed at certain positions on the mountain to monitor Jiutiao Kelian in real time and thus protect her. Specifically, a mountain can be described as a polyline, and the area below the polyline is rock. This polyline has $n$ vertices, and there is a pavilion at each vertex. The $i$-th vertex has coordinates $(i, h_i)$. Jiutiao Kelian can only play at pavilions, and the bodyguards also only monitor at pavilions. Due to technical reasons, a guard can only monitor all pavilions he can see whose x-coordinate does not exceed his own position. We say a guard can see a pavilion $p$ if and only if the segment connecting his own pavilion $q$ and $p$ does not pass through any rock. In particular, if this segment happens to pass exactly through any pavilion other than $p$ and $q$, then we consider that the guard cannot see Kelian. Hiring guards is expensive, so Kelian’s father wants as few guards as possible. Kelian’s father also wants a detailed hiring plan. He knows some pavilions may be under maintenance. He wants to compute, for all $1 \le l \le r \le n$: if it is known in advance that only the pavilions in the interval $[l, r]$ can be used for playing (and monitoring), what is the minimum number of guards needed so that every pavilion in $[l, r]$ is monitored. Kelian’s father has already obtained a result, and he hopes you can verify whether his result is correct.

The first line contains an integer $n$ denoting the number of pavilions. The second line contains $n$ integers, where the $i$-th integer $h_i$ means the $i$-th pavilion is at $(i, h_i)$.

For all $1 \le l \le r \le n$, compute the minimum number of guards needed if it is known in advance that Kelian will only play at pavilions in $[l, r]$, so that every pavilion in $[l, r]$ is monitored. Since the output would be too large, Kelian’s father only asks you to output the XOR of the answers for all $[l, r]$.

Sample Explanation: - If $r - l + 1 \le 2$, the answer is $1$. - If $l = 1$, $r = n$, then the answer is $2$, and two guards are needed at $(2,3)$ and $(3,1)$ to monitor Kelian. Constraints: - For $30\%$ of the testdata, $n \le 20$. - For $70\%$ of the testdata, $n \le 500$. - For $100\%$ of the testdata, $n \le 5000$, $1 \le h_i \le 10^9$. Translated by ChatGPT 5