Segment queries - MarisaOJ: Marisa Online Judge

Segment queries

Time limit: 1000 ms
Memory limit: 128 MB
Given a set containing empty line segments. Perform $q$ queries, each of which falls into one of two types: - `1 l r`: Add the line segment $(l,r)$ to the set. - `2 l r`: Count the number of line segments in the set that contain the line segment $(l,r)$. A line segment $(a,b)$ is said to contain $(l,r)$ if $a \leq l \leq r \leq b$. ### Input - The first line contains an integer $q$. - The next $q$ lines each contain a query in the specified format. ### Output - Print an integer, the answer for each query of type $2$. ### Constraints - $1 \leq q \leq 3 \times 10^5$. - $1 \leq l \leq r \leq 3 \times 10^5$. ### Example Input: ``` 5 1 1 5 1 1 3 2 2 4 1 3 3 2 2 2 ``` Output: ``` 1 2 ```