/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 525 点
問題文
数直線上に N 個の区間があり、1 から N までの番号が付けられています。
区間 i の左端の座標は 0、右端の座標は W_i です。ここで、W_1 < W_2 < \dots < W_N です。
Q 個のクエリが与えられるので、与えられた順に処理してください。クエリは次の 3 種類のいずれかです。
- タイプ 1 (
1 v): 現在の区間 v の左端の座標を l とする。番号が v 以下であるすべての区間をそれぞれ、左端の座標が l となるように平行移動する。 - タイプ 2 (
2 v): 現在の区間 v の右端の座標を r とする。番号が v 以下であるすべての区間をそれぞれ、右端の座標が r となるように平行移動する。 - タイプ 3 (
3 x): 座標 x+\frac{1}{2} を含む区間の現在の個数を出力する。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- W_1 < W_2 < \dots < W_N
- タイプ 1,2 のクエリで与えられる v について、1 \leq v \leq N
- タイプ 3 のクエリで与えられる x について、0 \leq x \leq 10^9
- タイプ 3 のクエリは少なくとも 1 つ与えられる
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
W_1 \dots W_N
Q
\textrm{query}_1
\textrm{query}_2
\vdots
\textrm{query}_Q
\textrm{query}_j は j 番目のクエリを表す。各クエリは以下のいずれかの形式で与えられる。
1 v
2 v
3 x
出力
タイプ 3 のクエリの回数を q として、q 行出力せよ。j 行目 (1 \leq j \leq q) には j 番目のタイプ 3 のクエリに対する答えを出力せよ。
入力例 1
4 2 4 6 10 5 2 3 1 2 3 2 2 4 3 1
出力例 1
4 1
はじめ、各区間は番号順に [0, 2], [0, 4], [0, 6], [0, 10] です。
- 1 番目のクエリにおいて、操作前の区間 3 の右端の座標は 6 なので、操作後の各区間は番号順に [4, 6], [2, 6], [0, 6], [0, 10] になります。
- 2 番目のクエリにおいて、操作前の区間 2 の左端の座標は 2 なので、操作後の各区間は番号順に [2, 4], [2, 6], [0, 6], [0, 10] になります。
- 3 番目のクエリにおいて、座標 2 + \frac{1}{2} を含む区間は区間 1,2,3,4 の 4 個なので、4 を出力します。
- 4 番目のクエリにおいて、操作前の区間 4 の右端の座標は 10 なので、操作後の各区間は番号順に [8, 10], [6, 10], [4, 10], [0, 10] になります。
- 5 番目のクエリにおいて、座標 1 + \frac{1}{2} を含む区間は区間 4 のみの 1 個なので、1 を出力します。
Score : 525 points
Problem Statement
There are N intervals on a number line, numbered from 1 to N.
The left endpoint of interval i is at coordinate 0, and the right endpoint is at coordinate W_i. Here, W_1 < W_2 < \dots < W_N.
You are given Q queries; process them in the order they are given. Each query is one of the following three types:
- Type 1 (
1 v): Let l be the coordinate of the current left endpoint of interval v. Translate each of the intervals numbered v or less so that its left endpoint is at coordinate l. - Type 2 (
2 v): Let r be the coordinate of the current right endpoint of interval v. Translate each of the intervals numbered v or less so that its right endpoint is at coordinate r. - Type 3 (
3 x): Output the current number of intervals that contain coordinate x+\frac{1}{2}.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- W_1 < W_2 < \dots < W_N
- For v given in queries of types 1 and 2, 1 \leq v \leq N.
- For x given in queries of type 3, 0 \leq x \leq 10^9.
- At least one query of type 3 is given.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
W_1 \dots W_N
Q
\textrm{query}_1
\textrm{query}_2
\vdots
\textrm{query}_Q
\textrm{query}_j represents the j-th query. Each query is given in one of the following formats:
1 v
2 v
3 x
Output
Let q be the number of queries of type 3, output q lines. The j-th line (1 \leq j \leq q) should contain the answer to the j-th query of type 3.
Sample Input 1
4 2 4 6 10 5 2 3 1 2 3 2 2 4 3 1
Sample Output 1
4 1
Initially, the intervals in order of their numbers are [0, 2], [0, 4], [0, 6], [0, 10].
- For the 1st query, the coordinate of the right endpoint of interval 3 before the operation is 6, so the intervals after the operation are [4, 6], [2, 6], [0, 6], [0, 10] in order of their numbers.
- For the 2nd query, the coordinate of the left endpoint of interval 2 before the operation is 2, so the intervals after the operation are [2, 4], [2, 6], [0, 6], [0, 10] in order of their numbers.
- For the 3rd query, the intervals that contain coordinate 2 + \frac{1}{2} are intervals 1,2,3,4, which is four intervals, so output 4.
- For the 4th query, the coordinate of the right endpoint of interval 4 before the operation is 10, so the intervals after the operation are [8, 10], [6, 10], [4, 10], [0, 10] in order of their numbers.
- For the 5th query, the intervals that contain coordinate 1 + \frac{1}{2} is only interval 4, which is one interval, so output 1.