23599번 - Segments 다국어

Innokentiy's job consists in writing all sorts of algorithms for processing triangular meshes. He is struggling with his most recent task, which requires quick building of plane sections of triangulations. Innokentiy realized that the key challenge of the task can be reduced to the following one-dimensional problem. Given are a set of segments on the coordinate plane, and queries to be processed: using a set point, define all segments containing this point. Help Innokentiy solve the problem.

To reflect the nature of real-life triangulations, the input data in this problem are generated randomly. Overall, $N$ segments of different lengths are provided, with many shorter segments and fewer longer segments. Each segment is defined by its center $C$ and the radius $R$, covering the interval between $C-R$ and $C+R$ inclusively. The center of each segment $C$ is generated with uniform a distribution between $0$ and $N$. The radius $R$ is generated using the following formula: $$\begin{equation*} R = \operatorname{min} \left( \frac{1}{\operatorname{rnd}}, N \right) \end{equation*}$$ where $\operatorname{rnd}$ returns a random number from $0$ to $1$ with a uniform distribution.

In addition, $N$ query points are provided. Each query is defined by a coordinate in the range between $0$ and $N$, also generated randomly with a uniform distribution. For each query, define all segments containing the point, and print the number of these segments.

In the real-life task, the answer must be returned instantly after receiving the query point. To model this situation, let's make the problem more dynamic: First, let's assume that initially the line contains no segments. The input dada lists $2 N$ queries, a half of them being segment addition queries, the other half being query points. We will process these queries in the same order in which they are listed, and consider only those segments which have already been added to the line by the time we begin proceeding a query point. Second, processing each query point changes all consecutive input data in the following way. Assume all segments containing the query point $P$ have the  numbers $k_0, k_1, k_2, \ldots, k_{t-1}$. Let $S = (k_0 + k_1 + \ldots + k_{t-1})$ be the sum of these numbers. Then the coordinate of all consecutive query points changes in the following manner: If $X$ is the current coordinate of the point, the new coordinate equals $(X + S) \operatorname{mod} N$. In other words, they must be shifted cyclically by $S$, thus bringing all values within the range of $0$ through $N$, excluding the value $N$. Similarly, the centers of all segments not yet added to the line must be changed as well.

The segments are numbered consecutively with numbers from $0$ to $N-1$ inclusively.

The first line of the input file contains an integer $N$ --- the number of segments and the number of points($3 \le N \le 10^5$). The remaining $2 N$ lines describe the queries in the order of their execution: a total of exactly $N$ queries for segment addition and $N$ query points.

A query point begins from the digit $1$, followed by a space-separated coordinate of the point $X$ as a real number ($0 \le X < N$). A segment addition query begins with the digit $0$, followed by two space-separated real numbers: $C$ --- the segment center and $R$ --- the segment radius ($0 \le C < N$, $0 < R \le N$).

All real numbers are defined with no more than six digits after the decimal point.

The output file must contain $N$ answers to query points in the order of their processing, one answer per line. For each query point, print only the number of the found segments $t$. The found segments, or rather, their numbers, must be used for correcting the remaining queries in the manner described in the problem statement.

First, a segment with its ends at $[-1.88721; 8.112790]$ is added. The immediately following query point belongs to this segment, hence the first answer equals 1. Since the number of the segment equals zero, no shift for the next queries is necessary.

Next, three segments are added with their centers and radii exactly as written in the file. Next, the query point at $x = 3.79801$ is checked, yielding two matching segments with the numbers 0 and 3. Now a shift of $3$ must be applied to all consecutive data$3$.

The next query point is defined in the file as equalling $2$, however, upon the execution of the cyclical shift by $3$ it falls into $0$. The point $x = 0$ belongs to the segments number 0, 1 and 2. Another cyclical shift of $3$ must be added, which, considering the already performed shift, produces a shift of $1$.

After the shift, the following query point equals $x = 4.845967$ and belongs to the segments number 0 and 3. Note that the point falls exactly on the right end of the segment 3. After this query, the total cyclical shift equals $4$.

Next, a segment with the center at $c = 2.630447$ is added, having taken the cyclical shift into account. Finally, the last query point at $x = 0.462071$ falls into the segments 0, 1, 2 and 4.