E. Welcome home, Chtholly

Codeforces

IDCF896E

Time3000ms

Memory512MB

Difficulty—

data structuresdsu

English · Original

Chinese · Translation

Formal · Original

%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, Chtholly Nota Seniorious miraculously returned from the fierce battle. As promised, Willem is now baking butter cake for her. However, although Willem is skilled in making dessert, he rarely bakes butter cake. This time, Willem made a big mistake — he accidentally broke the oven! Fortunately, Chtholly decided to help him. Willem puts _n_ cakes on a roll, cakes are numbered from 1 to _n_, the _i_\-th cake needs _a__i_ seconds of baking. Willem needs Chtholly to do _m_ operations to bake the cakes. Operation 1: 1 _l_ _r_ _x_ Willem 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_. Operation 2: 2 _l_ _r_ _x_ Willem 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_. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 105). The second line contains _n_ integers, _i_\-th of them is _a__i_ (1 ≤ _a__i_ ≤ 105). The next _m_ lines are the _m_ operations described above. It is guaranteed that 1 ≤ _l_ ≤ _r_ ≤ _n_ and 1 ≤ _x_ ≤ 105. ## Output For each operation of the second type, print the answer. [samples]

— 我……我活下来了。 — 欢迎回家，Chtholly。 — 我实现了我的承诺…… — 我做到了……我真的做到了！经过数日的战斗，Chtholly Nota Seniorious 奇迹般地从激烈的战斗中归来。正如承诺的那样，Willem 现在正在为她烤黄油蛋糕。然而，尽管 Willem 擅长制作甜点，但他很少烤黄油蛋糕。这次，Willem 犯了一个大错误——他不小心把烤箱弄坏了！幸运的是，Chtholly 决定帮助他。 Willem 将 #cf_span[n] 个蛋糕放在一个烤盘上，蛋糕编号从 #cf_span[1] 到 #cf_span[n]，第 #cf_span[i] 个蛋糕需要 #cf_span[ai] 秒的烘烤时间。 Willem 需要 Chtholly 执行 #cf_span[m] 次操作来烘烤这些蛋糕。操作 1：#cf_span[1 l r x] Willem 让 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]。操作 2：#cf_span[2 l r x] Willem 让 Chtholly 统计区间 #cf_span[[l, r]] 中恰好需要烘烤 #cf_span[x] 秒的蛋糕数量。更正式地，你需要找出区间 #cf_span[[l, r]] 中满足 #cf_span[ai = x] 的 #cf_span[i] 的个数。第一行包含两个整数 #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]。对于每个第二类操作，请输出答案。 ## Input 第一行包含两个整数 #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]。 ## Output 对于每个第二类操作，请输出答案。 [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of cakes and operations, respectively. Let $ 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 $. **Operations** For each operation $ j \in \{1, \dots, m\} $: - **Type 1** ($ 1\ l\ r\ x $): For all $ i \in [l, r] $, update $$ a_i \leftarrow \begin{cases} a_i - x & \text{if } a_i > x \\ a_i & \text{otherwise} \end{cases} $$ - **Type 2** ($ 2\ l\ r\ x $): Compute $$ \left| \left\{ i \in [l, r] \mid a_i = x \right\} \right| $$ **Constraints** 1. $ 1 \leq n, m \leq 10^5 $ 2. $ 1 \leq a_i \leq 10^5 $ for all $ i \in [1, n] $ 3. For each operation: $ 1 \leq l \leq r \leq n $, $ 1 \leq x \leq 10^5 $ **Objective** For each operation of Type 2, output the count of indices $ i \in [l, r] $ such that $ a_i = x $.

Samples

Input #1

Output #1

Input #2

7 7
1 9 2 6 8 1 7
2 1 7 1
2 2 5 2
1 4 7 7
2 2 4 2
1 3 4 5
2 3 3 3
2 3 7 2

Output #2

Input #3

8 13
75 85 88 100 105 120 122 128
1 1 8 70
2 3 8 30
1 3 8 3
2 2 5 15
1 2 4 10
2 1 5 5
1 2 7 27
2 1 5 5
1 3 7 12
1 1 7 4
2 1 8 1
1 4 8 5
2 1 8 1

Output #3

API Response (JSON)

{
  "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, Chtholl...",
      "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 犯了一个大错误——他不小心把烤箱弄坏...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments