D - Swap and Range Sum Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

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

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

  • 1 x : A_x と A_{x+1} の値を入れ替える。
  • 2 l r : \displaystyle \sum_{l\leq i\leq r} A_i の値を求める。

制約

  • 2\leq N \leq 2\times 10^5
  • 1\leq Q \leq 5\times 10^5
  • 1\leq A_i \leq 10^4
  • 1 種類目のクエリについて、1\leq x \leq N-1
  • 2 種類目のクエリについて、1\leq l\leq r \leq N
  • 入力は全て整数

入力

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

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

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

1 x

2 l r

出力

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

入力例 1

4 4
2 7 1 8
1 2
2 1 2
1 1
2 2 4

出力例 1

3
17
  • 1 番目のクエリでは、A_2 と A_3 の値を入れ替えます。これにより、A=(2,1,7,8) になります。
  • 2 番目のクエリでは、A_1+A_2 の値を求めます。答えは 2+1=3 です。
  • 3 番目のクエリでは、A_1 と A_2 の値を入れ替えます。これにより、A=(1,2,7,8) になります。
  • 4 番目のクエリでは、A_2+A_3+A_4 の値を求めます。答えは 2+7+8=17 です。

入力例 2

8 10
22 75 26 45 72 81 47 29
2 2 7
2 6 8
2 4 4
1 2
2 1 3
1 1
2 2 4
1 2
1 4
2 1 1

出力例 2

346
157
45
123
142
26

Score : 400 points

Problem Statement

You are given a sequence A=(A_1,A_2,\dots,A_N) of length N.

Process Q queries in order. Each query is in one of the following formats:

  • 1 x : Swap the values of A_x and A_{x+1}.
  • 2 l r : Find the value of \displaystyle \sum_{l\leq i\leq r} A_i.

Constraints

  • 2\leq N \leq 2\times 10^5
  • 1\leq Q \leq 5\times 10^5
  • 1\leq A_i \leq 10^4
  • For queries of the first type, 1\leq x \leq N-1.
  • For queries of the second type, 1\leq l\leq r \leq N.
  • All input values 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 represents the i-th query and is given in one of the following formats:

1 x

2 l r

Output

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

Sample Input 1

4 4
2 7 1 8
1 2
2 1 2
1 1
2 2 4

Sample Output 1

3
17
  • In the 1-st query, swap the values of A_2 and A_3. This makes A=(2,1,7,8).
  • In the 2-nd query, find the value of A_1+A_2. The answer is 2+1=3.
  • In the 3-rd query, swap the values of A_1 and A_2. This makes A=(1,2,7,8).
  • In the 4-th query, find the value of A_2+A_3+A_4. The answer is 2+7+8=17.

Sample Input 2

8 10
22 75 26 45 72 81 47 29
2 2 7
2 6 8
2 4 4
1 2
2 1 3
1 1
2 2 4
1 2
1 4
2 1 1

Sample Output 2

346
157
45
123
142
26