{"problem":{"name":"E. Welcome home, Chtholly","description":{"content":"%epigraph%%epigraphtext%_— I... I survived. — Welcome home, Chtholly. — I kept my promise... — I made it... I really made it! _%endepigraphtext%%endepigraph%After several days of fighting, Chtholl","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF896E"},"statements":[{"statement_type":"Markdown","content":"%epigraph%%epigraphtext%_— I... I survived.\n\n— Welcome home, Chtholly.\n\n— I kept my promise...\n\n— I made it... I really made it!\n\n_%endepigraphtext%%endepigraph%After several days of fighting, Chtholly Nota Seniorious miraculously returned from the fierce battle.\n\nAs promised, Willem is now baking butter cake for her.\n\nHowever, although Willem is skilled in making dessert, he rarely bakes butter cake.\n\nThis time, Willem made a big mistake — he accidentally broke the oven!\n\nFortunately, Chtholly decided to help him.\n\nWillem puts _n_ cakes on a roll, cakes are numbered from 1 to _n_, the _i_\\-th cake needs _a__i_ seconds of baking.\n\nWillem needs Chtholly to do _m_ operations to bake the cakes.\n\nOperation 1: 1 _l_ _r_ _x_\n\nWillem asks Chtholly to check each cake in the range \\[_l_, _r_\\], if the cake needs to be baked for more than _x_ seconds, he would bake it for _x_ seconds and put it back in its place. More precisely, for every _i_ in range \\[_l_, _r_\\], if _a__i_ is strictly more than _x_, _a__i_ becomes equal _a__i_ - _x_.\n\nOperation 2: 2 _l_ _r_ _x_\n\nWillem asks Chtholly to count the number of cakes in the range \\[_l_, _r_\\] that needs to be cooked for exactly _x_ seconds. More formally you should find number of such _i_ in range \\[_l_, _r_\\], that _a__i_ = _x_.\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 105).\n\nThe second line contains _n_ integers, _i_\\-th of them is _a__i_ (1 ≤ _a__i_ ≤ 105).\n\nThe next _m_ lines are the _m_ operations described above. It is guaranteed that 1 ≤ _l_ ≤ _r_ ≤ _n_ and 1 ≤ _x_ ≤ 105.\n\n## Output\n\nFor each operation of the second type, print the answer.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"— 我……我活下来了。\n\n— 欢迎回家，Chtholly。\n\n— 我实现了我的承诺……\n\n— 我做到了……我真的做到了！\n\n经过数日的战斗，Chtholly Nota Seniorious 奇迹般地从激烈的战斗中归来。\n\n正如承诺的那样，Willem 现在正在为她烤黄油蛋糕。\n\n然而，尽管 Willem 擅长制作甜点，但他很少烤黄油蛋糕。\n\n这次，Willem 犯了一个大错误——他不小心把烤箱弄坏了！\n\n幸运的是，Chtholly 决定帮助他。\n\nWillem 将 #cf_span[n] 个蛋糕放在一个烤盘上，蛋糕编号从 #cf_span[1] 到 #cf_span[n]，第 #cf_span[i] 个蛋糕需要 #cf_span[ai] 秒的烘烤时间。\n\nWillem 需要 Chtholly 执行 #cf_span[m] 次操作来烘烤这些蛋糕。\n\n操作 1：#cf_span[1 l r x]\n\nWillem 让 Chtholly 检查区间 #cf_span[[l, r]] 中的每个蛋糕，如果某个蛋糕需要烘烤的时间超过 #cf_span[x] 秒，则将其烘烤 #cf_span[x] 秒后放回原位。更准确地说，对于区间 #cf_span[[l, r]] 中的每个 #cf_span[i]，如果 #cf_span[ai] 严格大于 #cf_span[x]，则 #cf_span[ai] 变为 #cf_span[ai - x]。\n\n操作 2：#cf_span[2 l r x]\n\nWillem 让 Chtholly 统计区间 #cf_span[[l, r]] 中恰好需要烘烤 #cf_span[x] 秒的蛋糕数量。更正式地，你需要找出区间 #cf_span[[l, r]] 中满足 #cf_span[ai = x] 的 #cf_span[i] 的个数。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] #cf_span[(1 ≤ n, m ≤ 10^5)]。\n\n第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个是 #cf_span[ai] #cf_span[(1 ≤ ai ≤ 10^5)]。\n\n接下来的 #cf_span[m] 行是上述的 #cf_span[m] 个操作。保证 #cf_span[1 ≤ l ≤ r ≤ n] 且 #cf_span[1 ≤ x ≤ 10^5]。\n\n对于每个第二类操作，请输出答案。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m] #cf_span[(1 ≤ n, m ≤ 10^5)]。第二行包含 #cf_span[n] 个整数，第 #cf_span[i] 个是 #cf_span[ai] #cf_span[(1 ≤ ai ≤ 10^5)]。接下来的 #cf_span[m] 行是上述的 #cf_span[m] 个操作。保证 #cf_span[1 ≤ l ≤ r ≤ n] 且 #cf_span[1 ≤ x ≤ 10^5]。\n\n## Output\n\n对于每个第二类操作，请输出答案。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of cakes and operations, respectively.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i \\in [1, 10^5] $ represents the baking time required for cake $ i $.  \n\n**Operations**  \nFor each operation $ j \\in \\{1, \\dots, m\\} $:  \n- **Type 1** ($ 1\\ l\\ r\\ x $): For all $ i \\in [l, r] $, update  \n  $$\n  a_i \\leftarrow \n  \\begin{cases} \n  a_i - x & \\text{if } a_i > x \\\\\n  a_i & \\text{otherwise}\n  \\end{cases}\n  $$  \n- **Type 2** ($ 2\\ l\\ r\\ x $): Compute  \n  $$\n  \\left| \\left\\{ i \\in [l, r] \\mid a_i = x \\right\\} \\right|\n  $$\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 10^5 $  \n2. $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in [1, n] $  \n3. For each operation: $ 1 \\leq l \\leq r \\leq n $, $ 1 \\leq x \\leq 10^5 $\n\n**Objective**  \nFor each operation of Type 2, output the count of indices $ i \\in [l, r] $ such that $ a_i = x $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF896E","tags":["data structures","dsu"],"sample_group":[["5 6\n1 5 5 5 8\n2 2 5 5\n1 2 4 3\n2 2 5 2\n2 2 5 5\n1 3 5 1\n2 1 5 1","3\n3\n0\n3"],["7 7\n1 9 2 6 8 1 7\n2 1 7 1\n2 2 5 2\n1 4 7 7\n2 2 4 2\n1 3 4 5\n2 3 3 3\n2 3 7 2","2\n1\n1\n0\n1"],["8 13\n75 85 88 100 105 120 122 128\n1 1 8 70\n2 3 8 30\n1 3 8 3\n2 2 5 15\n1 2 4 10\n2 1 5 5\n1 2 7 27\n2 1 5 5\n1 3 7 12\n1 1 7 4\n2 1 8 1\n1 4 8 5\n2 1 8 1","1\n2\n3\n4\n5\n6"]],"created_at":"2026-03-03 11:00:39"}}