The Hermit
Time Limit: 25000/15000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 286 Accepted Submission(s): 183
Problem Description
The Hermit stands alone on the top of a mountain with a lantern in his hand. The snow-capped mountain range symbolises the Hermit’s spiritual achievement, growth and accomplishment. He has chosen this path of self-discovery and, as a result, has reached a heighted state of awareness
dhh loves to listen to radio. There are $N$ radio stations on a number axis, and the i-th station is located at $x_i$ = $i$. The broadcasting scope of the $i$-th station is $rad_i$ , which means stations in the interval [$i$ - $rad_i$ + 1, $i$ + $rad_i$ - 1] can receive the signal from the $i$-th station. For some unknown reason, the left boundary that can receive the $i$-th station’s signal is non-descending, which meansi $i$ - $rad_i$ + 1 ≤ $i$ + 1 - $rad_{i+1}$ + 1.
Now dhh wants to listen to the radio from station $i$, and he finds that the station $k$, satisfying both of the following conditions, can receive perfect signal from the station $i$:
k < i and station k can receive station i’s signal.
There exists another station $j$($k$ ≤ $j$ < $i$) such that station $k$ and $i$ can both receive the signal from station $j$ and the distance between station $k$ and $j$ is greater than or equal to the distance between station $j$ and $i$.
Now dhh wonders for each station $i$, how many stations can receive the perfect signal from station $i$.
dhh loves to listen to radio. There are $N$ radio stations on a number axis, and the i-th station is located at $x_i$ = $i$. The broadcasting scope of the $i$-th station is $rad_i$ , which means stations in the interval [$i$ - $rad_i$ + 1, $i$ + $rad_i$ - 1] can receive the signal from the $i$-th station. For some unknown reason, the left boundary that can receive the $i$-th station’s signal is non-descending, which meansi $i$ - $rad_i$ + 1 ≤ $i$ + 1 - $rad_{i+1}$ + 1.
Now dhh wants to listen to the radio from station $i$, and he finds that the station $k$, satisfying both of the following conditions, can receive perfect signal from the station $i$:
Now dhh wonders for each station $i$, how many stations can receive the perfect signal from station $i$.
Input
The first line of the input contains one integer $T$ ≤ 20, denoting the number of testcases. Then $T$ testcases follow. For each testcase:
The first line contains one positve integer $N$.
The second line contains $N$ positive integers $rad_1$, $rad_2$, ... , $rad_N$ .
It’s guaranteed that 1 ≤ $N$ ≤ $10^6$ ,$i$ - $rad_i$ + 1 ≥ 1 and $i$ + $rad_i$ - 1 ≤ $N$
It’s guaranteed that 1 ≤ $N$ ≤ $10^6$ ,$i$ - $rad_i$ + 1 ≥ 1 and $i$ + $rad_i$ - 1 ≤ $N$
Output
For the $k$-th testcase, output “Case $k$: $ans$” in one line, where $ans$ represents the xor result of answer for each radio station $i$.
xor is a bitwise operation, which takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison
of two bits, being 1 if the two bits are different, and 0 if they are the same.
xor is a bitwise operation, which takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. In this we perform the comparison
of two bits, being 1 if the two bits are different, and 0 if they are the same.
Sample Input
2 7 1 2 3 4 3 2 1 10 1 1 2 3 4 4 3 2 2 1
Sample Output
Case 1: 2 Case 2: 0
Source
642ccpc吉林
Hint
In the first testcase of the example, the number of stations that can receive the perfect signal from each station $i$ is respectively 0, 0, 1, 2, 1, 0, 0 in order, so the answer must be