E - Clamp 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

長さ N の整数列 A=(A_1, A_2, \dots, A_N) が与えられます。

Q 個のクエリが与えられるので、順に処理してください。 各クエリは以下のいずれかの形式です。

  • 1 x y : A_x の値を y に変更する。
  • 2 l r : \displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i)) の値を求める。

制約

  • 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
  • 1 種類目のクエリについて、
    • 1\leq x\leq N
    • 0\leq y \leq 5\times 10^5
  • 2 種類目のクエリについて、
    • 0\leq l,r \leq 5\times 10^5
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N Q
A_1 A_2 \dots A_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

ここで、\text{query}_i\ (1\leq i\leq Q) は i 番目のクエリを表し、以下のいずれかの形式で与えられる。

1 x y

2 l r

出力

2 種類目のクエリの個数を K として、K 行出力せよ。 i 行目 (1\leq i \leq K) には、2 種類目のクエリのうち i 個目のものに対する答えを出力せよ。

入力例 1

3 4
4 3 2
1 1 7
2 3 5
1 2 0
2 4 2

出力例 1

11
12

はじめ、A=(4,3,2) です。

  • 1 番目のクエリ：A_1 の値を 7 に変更します。A=(7,3,2) となります。
  • 2 番目のクエリ：\max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11 を出力します。
  • 3 番目のクエリ：A_2 の値を 0 に変更します。A=(7,0,2) となります。
  • 4 番目のクエリ：\max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12 を出力します。

入力例 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

出力例 2

3824
2032
2073
4350
3596
4884

Score : 450 points

Problem Statement

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

Output

Let K be the number of queries of the second type. Output K lines. The i-th line (1\leq i \leq K) should contain the answer to the i-th query of the second type.

Sample Input 1

3 4
4 3 2
1 1 7
2 3 5
1 2 0
2 4 2

Sample 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.

Sample 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

Sample Output 2

3824
2032
2073
4350
3596
4884