Clamp

AtCoder

IDabc432_e

Time2000ms

Memory256MB

Difficulty—

You are given an integer sequence $A=(A_1, A_2, \dots, A_N)$ of length $N$. You are given $Q$ queries, which you should process in order. Each query is in one of the following formats: * `1 x y` : Change the value of $A_x$ to $y$. * `2 l r` : Find the value of $\displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i))$. ## Constraints * $1\leq N \leq 5\times 10^5$ * $1\leq Q \leq 2\times 10^5$ * $0\leq A_i \leq 5\times 10^5$ * For queries of the first type, * $1\leq x\leq N$ * $0\leq y \leq 5\times 10^5$ * For queries of the second type, * $0\leq l,r \leq 5\times 10^5$ * All inputs are integers. ## Input The input is given from Standard Input in the following format: $N$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$ Here, $\text{query}_i\ (1\leq i\leq Q)$ represents the $i$\-th query and is given in one of the following formats: $1$ $x$ $y$ $2$ $l$ $r$ [samples]

Samples

Input #1

Output #1

11
12

Initially, $A=(4,3,2)$.

*   First query: Change the value of $A_1$ to $7$. $A$ becomes $(7,3,2)$.
*   Second query: Output $\max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11$.
*   Third query: Change the value of $A_2$ to $0$. $A$ becomes $(7,0,2)$.
*   Fourth query: Output $\max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12$.

Input #2

8 10
320 578 244 604 145 839 156 857
2 400 556
1 5 168
2 254 62
2 145 301
1 1 23
1 3 0
2 413 758
2 297 613
1 8 451
2 598 692

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Clamp",
    "description": {
      "content": "You are given an integer sequence $A=(A_1, A_2, \\dots, A_N)$ of length $N$. You are given $Q$ queries, which you should process in order. Each query is in one of the following formats: *   `1 x y` : ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc432_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer sequence $A=(A_1, A_2, \\dots, A_N)$ of length $N$.\nYou are given $Q$ queries, which you should process in order. Each query is in one of the following formats:\n\n*   `1 x y` : ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments