P8861 线段

有一个初始为空的线段集，你需要处理 $q$ 组询问，每组询问的格式为如下三种之一： 1. 加入一条新线段 $[l_i,r_i]$。 2. 将线段集里所有与 $[l_i,r_i]$ 相交的线段修改为其与 $[l_i,r_i]$ 的交。 3. 求出线段集里所有与 $[l_i,r_i]$ 相交的线段与 $[l_i,r_i]$ 的交的长度和。 两条线段 $[a,b],[c,d]$ 相交，当且仅当 $\max\{a,c\} \leq \min\{b,d\}$，它们的交为 $[\max\{a,c\},\min\{b,d\}]$。 一条线段 $[a,b]$ 的长度为 $b-a$。 在部分测试点中，你需要**在线地**进行这些操作。 **注意：在本题中，线段可能退化为单点。**

无

无

#### 【样例解释】 每次操作后的线段集： - 第一次后：$\{ [1,5] \}$ - 第二次后：$\{ [1,5],[6,8] \}$ - 第三次后：$\{ [1,5],[6,8],[2,3] \}$ - 第五次后：$\{ [4,5],[6,6],[2,3] \}$ - 第六次后：$\{ [4,5],[6,6],[2,3],[5,9] \}$ - 第七次后：$\{ [4,5],[6,6],[2,3],[5,7] \}$ #### 【数据范围】 记 $k_1,k_2,k_3$ 分别为 $opt=1,2,3$ 的询问个数。 | 测试点编号 | $k_1 \leq$ | $k_2 \leq$ | $k_3 \leq$ | $type=$ | 特殊性质 | |:----------------:|:---------------:|:---------------:|:---------------:|:-------:|:--------------------------------:| | $1 \sim 2$ | $100$ | $100$ | $100$ | $=0$ | 无 | | $3 \sim 5$ | $10^5$ | $5$ | $3 \times 10^5$ | $=0$ | 无 | | $6 \sim 8$ | $10^5$ | $10^5$ | $1$ | $=0$ | 所有 $2$ 操作在所有 $1$ 操作之后 | | $9 \sim 12$ | $10^5$ | $10^5$ | $3 \times 10^5$ | $=0$ | 所有 $2$ 操作在所有 $1$ 操作之后 | | $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$ | 无 | | $21 \sim 25$ | $10^5$ | $10^5$ | $3 \times 10^5$ | $=1$ | 无 | 对于所有数据，$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 \leq1$，$1 \leq opt \leq 3$。