{"problem":{"name":"F. Nagini","description":{"content":"Nagini, being a horcrux You-know-who created with the murder of Bertha Jorkins, has accumulated its army of snakes and is launching an attack on Hogwarts school. Hogwarts' entrance can be imagined as","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF855F"},"statements":[{"statement_type":"Markdown","content":"Nagini, being a horcrux You-know-who created with the murder of Bertha Jorkins, has accumulated its army of snakes and is launching an attack on Hogwarts school.\n\nHogwarts' entrance can be imagined as a straight line (x-axis) from 1 to 105. Nagini is launching various snakes at the Hogwarts entrance. Each snake lands parallel to the entrance, covering a segment at a distance _k_ from _x_ = _l_ to _x_ = _r_. Formally, each snake can be imagined as being a line segment between points (_l_, _k_) and (_r_, _k_). Note that _k_ can be both positive and negative, but not 0.\n\nLet, at some _x_\\-coordinate _x_ = _i_, there be snakes at point (_i_, _y_1) and point (_i_, _y_2), such that _y_1 > 0 and _y_2 < 0. Then, if for any point (_i_, _y_3) containing a snake such that _y_3 > 0, _y_1 ≤ _y_3 holds and for any point (_i_, _y_4) containing a snake such that _y_4 < 0, |_y_2| ≤ |_y_4| holds, then the danger value at coordinate _x_ = _i_ is _y_1 + |_y_2|. If no such _y_1 and _y_2 exist, danger value is 0.\n\nHarry wants to calculate the danger value of various segments of the Hogwarts entrance. Danger value for a segment \\[_l_, _r_) of the entrance can be calculated by taking the sum of danger values for each integer _x_\\-coordinate present in the segment.\n\nFormally, you have to implement two types of queries:\n\n*   _1 l r k_: a snake is added parallel to entrance from _x_ = _l_ to _x_ = _r_ at y-coordinate _y_ = _k_ (_l_ inclusive, _r_ exclusive).\n*   _2 l r_: you have to calculate the danger value of segment _l_ to _r_ (_l_ inclusive, _r_ exclusive).\n\n## Input\n\nFirst line of input contains a single integer _q_ (1 ≤ _q_ ≤ 5·104) denoting the number of queries.\n\nNext _q_ lines each describe a query. Each query description first contains the query type _type__i_ (1 ≤ _type__i_ ≤ 2). This is followed by further description of the query. In case of the type being 1, it is followed by integers _l__i_, _r__i_ and _k__i_ (,  - 109 ≤ _k__i_ ≤ 109, _k_ ≠ 0). Otherwise, it just contains two integers, _l__i_ and _r__i_ (1 ≤ _l__i_ < _r__i_ ≤ 105).\n\n## Output\n\nOutput the answer for each query of type 2 in a separate line.\n\n[samples]\n\n## Note\n\nIn the first sample case, the danger value for _x_\\-coordinates 1 is 0 as there is no _y_2 satisfying the above condition for _x_ = 1.\n\nDanger values for _x_\\-coordinates 2 and 3 is 10 + | - 7| = 17.\n\nDanger values for _x_\\-coordinates 4 to 9 is again 0 as there is no _y_2 satisfying the above condition for these coordinates.\n\nThus, total danger value is 17 + 17 = 34.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Nagini 作为伏地魔用杀害伯莎·乔金斯所制造的魂器，已经集结了它的蛇群，并对霍格沃茨学校发动了攻击。\n\n霍格沃茨的入口可以被想象为一条从 #cf_span[1] 到 #cf_span[105] 的直线（x 轴）。Nagini 正在向霍格沃茨入口发射各种蛇。每条蛇都平行于入口落地，覆盖在距离 #cf_span[x = l] 到 #cf_span[x = r] 处、距离为 #cf_span[k] 的线段上。形式上，每条蛇可以被看作连接点 #cf_span[(l, k)] 和 #cf_span[(r, k)] 的线段。注意，#cf_span[k] 可以为正或负，但不能为 #cf_span[0]。\n\n设在某个 #cf_span[x]-坐标 #cf_span[x = i] 处，存在蛇位于点 #cf_span[(i, y1)] 和点 #cf_span[(i, y2)]，满足 #cf_span[y1 > 0] 且 #cf_span[y2 < 0]。那么，若对任意包含蛇的点 #cf_span[(i, y3)]（其中 #cf_span[y3 > 0]），均有 #cf_span[y1 ≤ y3] 成立，且对任意包含蛇的点 #cf_span[(i, y4)]（其中 #cf_span[y4 < 0]），均有 #cf_span[|y2| ≤ |y4|] 成立，则坐标 #cf_span[x = i] 的危险值为 #cf_span[y1 + |y2|]。若不存在满足上述条件的 #cf_span[y1] 和 #cf_span[y2]，则危险值为 #cf_span[0]。\n\n哈利希望计算霍格沃茨入口各段的危险值。入口段 #cf_span[[l, r)] 的危险值可以通过对该段中每个整数 #cf_span[x]-坐标的危险值求和得到。\n\n形式上，你需要实现两种类型的查询：\n\n输入的第一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 5·10^4]），表示查询数量。\n\n接下来的 #cf_span[q] 行每行描述一个查询。每个查询首先包含查询类型 #cf_span[typei]（#cf_span[1 ≤ typei ≤ 2]）。随后是该查询的进一步描述：若类型为 #cf_span[1]，则后跟整数 #cf_span[li, ri] 和 #cf_span[ki]（#cf_span[ - 10^9 ≤ ki ≤ 10^9]，#cf_span[k ≠ 0]）；否则，仅包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 10^5]）。\n\n对每个类型为 2 的查询，在单独一行输出答案。\n\n在第一个样例中，#cf_span[x]-坐标 #cf_span[1] 的危险值为 #cf_span[0]，因为不存在满足上述条件的 #cf_span[y2]（当 #cf_span[x = 1] 时）。\n\n#cf_span[x]-坐标 #cf_span[2] 和 #cf_span[3] 的危险值为 #cf_span[10 + | - 7| = 17]。\n\n#cf_span[x]-坐标 #cf_span[4] 到 #cf_span[9] 的危险值再次为 #cf_span[0]，因为这些坐标上不存在满足条件的 #cf_span[y2]。\n\n因此，总危险值为 #cf_span[17 + 17 = 34]。\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 5·10^4]），表示查询数量。接下来的 #cf_span[q] 行每行描述一个查询。每个查询首先包含查询类型 #cf_span[typei]（#cf_span[1 ≤ typei ≤ 2]）。随后是该查询的进一步描述：若类型为 #cf_span[1]，则后跟整数 #cf_span[li, ri] 和 #cf_span[ki]（#cf_span[ - 10^9 ≤ ki ≤ 10^9]，#cf_span[k ≠ 0]）；否则，仅包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li < ri ≤ 10^5]）。\n\n## Output\n\n对每个类型为 2 的查询，在单独一行输出答案。\n\n[samples]\n\n## Note\n\n在第一个样例中，#cf_span[x]-坐标 #cf_span[1] 的危险值为 #cf_span[0]，因为不存在满足上述条件的 #cf_span[y2]（当 #cf_span[x = 1] 时）。#cf_span[x]-坐标 #cf_span[2] 和 #cf_span[3] 的危险值为 #cf_span[10 + | - 7| = 17]。#cf_span[x]-坐标 #cf_span[4] 到 #cf_span[9] 的危险值再次为 #cf_span[0]，因为这些坐标上不存在满足条件的 #cf_span[y2]。因此，总危险值为 #cf_span[17 + 17 = 34]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ Q \\in \\mathbb{Z} $ be the number of queries.  \nLet $ S \\subseteq \\mathbb{Z} \\times \\mathbb{Z} $ be the set of snake segments, where each element $ (l, r, k) \\in S $ represents a horizontal segment from $ (l, k) $ to $ (r, k) $, with $ k \\ne 0 $.  \n\nFor any integer coordinate $ x \\in [1, 10^5] $:  \n- Let $ P_x = \\{ k \\mid (l, r, k) \\in S \\text{ and } l \\le x < r \\} $ be the set of vertical positions of snakes covering $ x $.  \n- Let $ P_x^+ = \\{ k \\in P_x \\mid k > 0 \\} $, $ P_x^- = \\{ k \\in P_x \\mid k < 0 \\} $.  \n- Define the **danger value** at $ x $ as:  \n  $$\n  d(x) = \n  \\begin{cases}\n  \\max P_x^+ + |\\min P_x^-| & \\text{if } P_x^+ \\ne \\emptyset \\text{ and } P_x^- \\ne \\emptyset, \\\\\n  0 & \\text{otherwise}.\n  \\end{cases}\n  $$\n\n**Constraints**  \n1. $ 1 \\le Q \\le 5 \\cdot 10^4 $  \n2. For each query:  \n   - Type 1: $ 1 \\le l_i < r_i \\le 10^5 $, $ -10^9 \\le k_i \\le 10^9 $, $ k_i \\ne 0 $  \n   - Type 2: $ 1 \\le l_i < r_i \\le 10^5 $  \n\n**Objective**  \nFor each query:  \n- If type 1: Add segment $ (l_i, r_i, k_i) $ to $ S $.  \n- If type 2: Compute $ \\sum_{x = l_i}^{r_i - 1} d(x) $ and output the result.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF855F","tags":["binary search","data structures"],"sample_group":[["3\n1 1 10 10\n1 2 4 -7\n2 1 10","34"],["7\n1 2 3 5\n1 1 10 10\n1 4 5 -5\n2 4 8\n1 1 10 -10\n2 4 8\n2 1 10","15\n75\n170"]],"created_at":"2026-03-03 11:00:39"}}