E - 本棚の整理 解説 /

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

配点 : 466 点

問題文

高橋君は図書館の司書をしています。図書館には横一列に並んだ N 個の棚があり、左から順に棚 1, 2, \ldots, N と番号が付いています。

最初、各棚に置かれている本の冊数は 0 です。高橋君はこれから Q 回の作業を順番に行います。各作業は以下の 3 種類のいずれかです。

  • 作業 1 : 整数 l, r が与えられる。棚 l, l+1, \ldots, r のそれぞれに本を 1 冊ずつ追加する。すなわち、この範囲に含まれる各棚の冊数が 1 増える。
  • 作業 2 : 整数 p が与えられる。棚 p にある本をすべて取り除き、棚 p の冊数を 0 にする。（冊数がすでに 0 の場合は何も起こらない。）
  • 作業 3 : 整数 l, r が与えられる。棚 l, l+1, \ldots, r に現在置かれている本の合計冊数を求める。

各作業 3 について、答えを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 作業 1 および作業 3 において、1 \leq l \leq r \leq N
  • 作業 2 において、1 \leq p \leq N
  • 作業 3 は少なくとも 1 回存在する
  • 入力はすべて整数である
  • 各作業 3 の時点での答えは 0 以上 2^{63} - 1 以下であることが保証される（すなわち符号付き 64 ビット整数に収まる）

入力

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • 1 行目には、棚の数を表す整数 N と作業の回数を表す整数 Q が、スペース区切りで与えられる。
  • 続く Q 行にわたって、各作業の内容が 1 行ずつ与えられる。i 番目の作業 \mathrm{query}_i の形式は、作業の種類に応じて以下のとおりである。
  • 作業 1 の場合 : 1 l r — 棚 l から棚 r までの各棚に本を 1 冊ずつ追加する。ここで l は範囲の左端、r は範囲の右端を表す棚番号である。
  • 作業 2 の場合 : 2 p — 棚 p の本をすべて取り除き、冊数を 0 にする。ここで p は対象の棚番号である。
  • 作業 3 の場合 : 3 l r — 棚 l から棚 r までの本の合計冊数を求める。ここで l は範囲の左端、r は範囲の右端を表す棚番号である。

出力

作業 3 が与えられるたびに、その時点での該当範囲の本の合計冊数を 1 行に出力せよ。すべての作業 3 の答えを、入力で与えられた順に出力すること。

入力例 1

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

出力例 1

0
3
3
1

入力例 2

3 8
2 2
3 1 3
1 1 1
1 1 3
3 1 1
2 1
3 1 2
3 3 3

出力例 2

0
2
1
1

入力例 3

10 16
1 1 10
1 3 7
3 1 10
2 5
3 4 6
1 5 5
1 6 10
3 5 10
2 10
1 1 3
3 1 3
2 1
2 5
3 1 10
1 2 9
3 7 9

出力例 3

15
4
13
7
17
10

入力例 4

30 30
1 1 30
1 1 15
1 16 30
3 1 30
2 1
2 30
3 1 5
1 5 25
3 20 30
2 10
2 20
1 10 20
3 10 20
1 1 1
1 30 30
3 1 30
2 15
1 14 16
3 14 16
1 2 29
2 16
3 15 17
1 1 30
3 1 1
2 1
3 1 30
1 7 7
2 7
3 7 7
3 28 30

出力例 4

60
8
26
38
84
11
7
2
133
0
10

入力例 5

1 7
3 1 1
2 1
1 1 1
1 1 1
3 1 1
2 1
3 1 1

出力例 5

0
2
0

Score : 466 pts

Problem Statement

Takahashi works as a librarian at a library. The library has N shelves arranged in a horizontal row, numbered 1, 2, \ldots, N from left to right.

Initially, the number of books on each shelf is 0. Takahashi will perform Q operations in order. Each operation is one of the following three types:

  • Operation 1: Given integers l, r. Add 1 book to each of shelves l, l+1, \ldots, r. That is, the number of books on each shelf in this range increases by 1.
  • Operation 2: Given an integer p. Remove all books from shelf p, setting the number of books on shelf p to 0. (If the number of books is already 0, nothing happens.)
  • Operation 3: Given integers l, r. Find the total number of books currently placed on shelves l, l+1, \ldots, r.

For each Operation 3, output the answer.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • For Operations 1 and 3, 1 \leq l \leq r \leq N
  • For Operation 2, 1 \leq p \leq N
  • There is at least one Operation 3
  • All input values are integers
  • It is guaranteed that the answer at the time of each Operation 3 is between 0 and 2^{63} - 1, inclusive (i.e., it fits in a signed 64-bit integer)

Input

N Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
  • The first line contains an integer N representing the number of shelves and an integer Q representing the number of operations, separated by a space.
  • The following Q lines each describe one operation. The format of the i-th operation \mathrm{query}_i depends on the type of operation:
  • Operation 1: 1 l r — Add 1 book to each shelf from shelf l to shelf r. Here, l is the shelf number of the left endpoint and r is the shelf number of the right endpoint of the range.
  • Operation 2: 2 p — Remove all books from shelf p, setting the number of books to 0. Here, p is the target shelf number.
  • Operation 3: 3 l r — Find the total number of books from shelf l to shelf r. Here, l is the shelf number of the left endpoint and r is the shelf number of the right endpoint of the range.

Output

Each time Operation 3 is given, output the total number of books in the specified range at that point in time on a single line. Output the answers for all Operation 3s in the order they appear in the input.

Sample Input 1

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

Sample Output 1

0
3
3
1

Sample Input 2

3 8
2 2
3 1 3
1 1 1
1 1 3
3 1 1
2 1
3 1 2
3 3 3

Sample Output 2

0
2
1
1

Sample Input 3

10 16
1 1 10
1 3 7
3 1 10
2 5
3 4 6
1 5 5
1 6 10
3 5 10
2 10
1 1 3
3 1 3
2 1
2 5
3 1 10
1 2 9
3 7 9

Sample Output 3

15
4
13
7
17
10

Sample Input 4

30 30
1 1 30
1 1 15
1 16 30
3 1 30
2 1
2 30
3 1 5
1 5 25
3 20 30
2 10
2 20
1 10 20
3 10 20
1 1 1
1 30 30
3 1 30
2 15
1 14 16
3 14 16
1 2 29
2 16
3 15 17
1 1 30
3 1 1
2 1
3 1 30
1 7 7
2 7
3 7 7
3 28 30

Sample Output 4

60
8
26
38
84
11
7
2
133
0
10

Sample Input 5

1 7
3 1 1
2 1
1 1 1
1 1 1
3 1 1
2 1
3 1 1

Sample Output 5

0
2
0