{"problem":{"name":"线段","description":{"content":"有一个初始为空的线段集，你需要处理 $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]$ 相交，当且仅当 $\\","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8861"},"statements":[{"statement_type":"Markdown","content":"有一个初始为空的线段集，你需要处理 $q$ 组询问，每组询问的格式为如下三种之一：\n\n1. 加入一条新线段 $[l_i,r_i]$。\n2. 将线段集里所有与 $[l_i,r_i]$ 相交的线段修改为其与 $[l_i,r_i]$ 的交。\n3. 求出线段集里所有与 $[l_i,r_i]$ 相交的线段与 $[l_i,r_i]$ 的交的长度和。\n\n两条线段 $[a,b],[c,d]$ 相交，当且仅当 $\\max\\{a,c\\} \\leq \\min\\{b,d\\}$，它们的交为 $[\\max\\{a,c\\},\\min\\{b,d\\}]$。\n\n一条线段 $[a,b]$ 的长度为 $b-a$。\n\n在部分测试点中，你需要**在线地**进行这些操作。\n\n**注意：在本题中，线段可能退化为单点。**\n\n## Input\n\n第一行两个正整数 $q$ 和 $type$，分别表示操作次数和强制在线参数。\n\n接下来 $q$ 行，每行三个正整数 $opt,l_i',r_i'$，其中 $opt$ 表示操作类型。\n\n我们记 $last$ 表示上一次 $3$ 询问的答案（$last$ 初始为 $0$），则真实的 $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 )$。\n\n数据保证 $1 \\leq l_i \\leq r_i \\leq 2 \\times 10^5$。\n\n## Output\n\n对于每个 $3$ 询问，输出一行表示答案。\n\n[samples]\n\n## Note\n\n#### 【样例解释】\n\n每次操作后的线段集：\n\n- 第一次后：$\\{ [1,5] \\}$\n- 第二次后：$\\{ [1,5],[6,8] \\}$\n- 第三次后：$\\{ [1,5],[6,8],[2,3] \\}$\n- 第五次后：$\\{ [4,5],[6,6],[2,3] \\}$\n- 第六次后：$\\{ [4,5],[6,6],[2,3],[5,9] \\}$\n- 第七次后：$\\{ [4,5],[6,6],[2,3],[5,7] \\}$\n\n#### 【数据范围】\n\n记 $k_1,k_2,k_3$ 分别为 $opt=1,2,3$ 的询问个数。\n\n|    测试点编号    |    $k_1 \\leq$    |    $k_2 \\leq$    |    $k_3 \\leq$    | $type=$ |             特殊性质             |\n|:----------------:|:---------------:|:---------------:|:---------------:|:-------:|:--------------------------------:|\n|      $1 \\sim 2$  |      $100$      |      $100$      |      $100$      |   $=0$  |                无                |\n|      $3 \\sim 5$  |      $10^5$     |       $5$       | $3 \\times 10^5$ |   $=0$  |                无                |\n|      $6 \\sim 8$  |      $10^5$     |      $10^5$     |        $1$        |   $=0$  | 所有 $2$ 操作在所有 $1$ 操作之后 |\n|      $9 \\sim 12$ |      $10^5$     |      $10^5$     | $3 \\times 10^5$ |   $=0$  | 所有 $2$ 操作在所有 $1$ 操作之后 |\n|     $13 \\sim 17$ |      $10^5$     |      $10^5$     | $3 \\times 10^5$ |   $=0$  |     $l_i \\leq 10^5 \\leq r_i$     |\n|     $18 \\sim 20$ | $5 \\times 10^4$ | $5 \\times 10^4$ | $3 \\times 10^5$ |   $=0$  |                无                |\n|     $21 \\sim 25$ |      $10^5$     |      $10^5$     | $3 \\times 10^5$ |   $=1$  |                无                |\n\n对于所有数据，$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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8861","tags":["线段树","堆","洛谷原创","O2优化","分治","洛谷月赛"],"sample_group":[["9 0\n1 1 5\n1 6 8\n1 2 3\n3 3 8\n2 4 6\n1 5 9\n2 2 7\n3 2 7\n3 3 6\n","4\n4\n2\n"]],"created_at":"2026-03-03 11:09:25"}}