P8861 Segments

There is an initially empty set of segments. You need to process $q$ queries. Each query is in one of the following three forms: 1. Add a new segment $[l_i, r_i]$. 2. For all segments in the set that intersect with $[l_i, r_i]$, modify each of them into its intersection with $[l_i, r_i]$. 3. Compute the sum of lengths of the intersections between $[l_i, r_i]$ and all segments in the set that intersect with $[l_i, r_i]$. Two segments $[a,b]$ and $[c,d]$ intersect if and only if $\max\{a,c\} \leq \min\{b,d\}$. Their intersection is $[\max\{a,c\}, \min\{b,d\}]$. The length of a segment $[a,b]$ is $b-a$. In some test points, you need to perform these operations **online**. **Note: In this problem, a segment may degenerate into a single point.**

The first line contains two positive integers $q$ and $type$, representing the number of operations and the forced online parameter. The next $q$ lines each contain three positive integers $opt, l_i', r_i'$, where $opt$ indicates the operation type. Let $last$ be the answer to the previous type $3$ query ($last$ is initially $0$). Then the real values are $l_i = ( l_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 )$, $r_i = ( r_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 )$. The data guarantees that $1 \leq l_i \leq r_i \leq 2 \times 10^5$.

For each type $3$ query, output one line containing the answer.

#### Sample Explanation The set of segments after each operation: - After the first: $\{ [1,5] \}$ - After the second: $\{ [1,5],[6,8] \}$ - After the third: $\{ [1,5],[6,8],[2,3] \}$ - After the fifth: $\{ [4,5],[6,6],[2,3] \}$ - After the sixth: $\{ [4,5],[6,6],[2,3],[5,9] \}$ - After the seventh: $\{ [4,5],[6,6],[2,3],[5,7] \}$ #### Constraints Let $k_1, k_2, k_3$ be the numbers of queries with $opt=1,2,3$, respectively. | Test Point ID | $k_1 \leq$ | $k_2 \leq$ | $k_3 \leq$ | $type=$ | Special Property | |:-------------------:|:---------------:|:---------------:|:---------------:|:-------:|:----------------------------------------:| | $1 \sim 2$ | $100$ | $100$ | $100$ | $=0$ | None | | $3 \sim 5$ | $10^5$ | $5$ | $3 \times 10^5$ | $=0$ | None | | $6 \sim 8$ | $10^5$ | $10^5$ | $1$ | $=0$ | All type $2$ operations are after all type $1$ operations | | $9 \sim 12$ | $10^5$ | $10^5$ | $3 \times 10^5$ | $=0$ | All type $2$ operations are after all type $1$ operations | | $13 \sim 17$ | $10^5$ | $10^5$ | $3 \times 10^5$ | $=0$ | $l_i \leq 10^5 \leq r_i$ | | $18 \sim 20$ | $5 \times 10^4$ | $5 \times 10^4$ | $3 \times 10^5$ | $=0$ | None | | $21 \sim 25$ | $10^5$ | $10^5$ | $3 \times 10^5$ | $=1$ | None | For all data, $1 \leq q \leq 5 \times 10^5$, $k_3 \geq 1$, $0 \leq l_i', r_i' \leq 2 \times 10^5$, $1 \leq l_i \leq r_i \leq 2 \times 10^5$, $0 \leq type \leq 1$, $1 \leq opt \leq 3$. Translated by ChatGPT 5