AtCoder Weekday Contest 0106 Beta

A - 平坦な区間の判定

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

配点 : 233 点

問題文

高橋君は、線路の保守点検を行っています。線路沿いには N 個の計測地点があり、地点 i（1 \leq i \leq N）における線路の高さは H_i です。

連続する K 個の地点の高さがすべて同じ値であるとき、その区間を平坦な区間と呼びます。より正確には、ある整数 l（1 \leq l \leq N - K + 1）について、H_l = H_{l+1} = \cdots = H_{l+K-1} が成り立つとき、地点 l, l+1, \ldots, l+K-1 からなる区間は平坦な区間です。

平坦な区間が一つでも存在するかどうかを判定してください。

制約

1 \leq K \leq N \leq 2 \times 10^5
0 \leq H_i \leq 10^9
入力はすべて整数である。

入力

N K
H_1
H_2
\vdots
H_N

1 行目には、計測地点の数 N と平坦な区間の長さ K がスペース区切りで与えられる。
続く N 行のうち i 行目（1 \leq i \leq N）には、地点 i の高さ H_i が与えられる。

出力

平坦な区間が存在する場合は Yes を、存在しない場合は No を 1 行に出力せよ。

入力例 1

出力例 1

Yes

入力例 2

出力例 2

No

入力例 3

出力例 3

Yes

入力例 4

出力例 4

No

入力例 5

1 1
1000000000

出力例 5

Yes

Score : 233 pts

Problem Statement

Takahashi is performing maintenance inspections on a railway track. There are N measurement points along the track, and the height of the track at point i (1 \leq i \leq N) is H_i.

When K consecutive points all have the same height, that interval is called a flat interval. More precisely, for some integer l (1 \leq l \leq N - K + 1), if H_l = H_{l+1} = \cdots = H_{l+K-1} holds, then the interval consisting of points l, l+1, \ldots, l+K-1 is a flat interval.

Determine whether at least one flat interval exists.

Constraints

1 \leq K \leq N \leq 2 \times 10^5
0 \leq H_i \leq 10^9
All inputs are integers.

Input

N K
H_1
H_2
\vdots
H_N

The first line contains the number of measurement points N and the length of a flat interval K, separated by a space.
The i-th line (1 \leq i \leq N) of the following N lines contains the height H_i of point i.

Output

If a flat interval exists, print Yes; otherwise, print No on a single line.

Sample Input 1

Sample Output 1

Yes

Sample Input 2

Sample Output 2

No

Sample Input 3

Sample Output 3

Yes

Sample Input 4

Sample Output 4

No

Sample Input 5

1 1
1000000000

Sample Output 5

Yes

B - 山岳地帯の雨水シミュレーション

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

配点 : 300 点

問題文

高橋君は、山岳地帯の地形シミュレーションを行っています。

山岳地帯には N 個の地点があり、各地点には番号 1 から N が付けられています。地点 i の標高は H_i であり、初期時点で W_i リットルの雨水が溜まっています。

地点同士は M 本の水路で結ばれています。j 番目の水路は地点 U_j と地点 V_j を双方向に結んでいます。水は標高が高い地点から低い地点へのみ流れます。すなわち、水路で結ばれた2地点の標高が等しい場合、その水路を通じて水は流れません。

ある地点 v に対し、水路で直接結ばれた地点のうち標高が v より厳密に低い地点を、v の下流隣接地点と呼ぶことにします。

高橋君は、K 個の地点にダムを設置しました（K = 0 の場合、ダムは1つも設置されません）。ダムが設置された地点の番号は S_1, S_2, \ldots, S_K です。ダムが設置された地点では、水路を通じて他の地点から水が流入することはありますが、その地点から水が流れ出すことは一切ありません。

各地点の水の流出は、以下の手順で処理されます。

すべての地点を標高の高い順に並べます。標高が同じ地点間では水が流れないため、同じ標高の地点同士の順序は任意で構いません（処理順序によって結果は変わりません）。
この順に各地点を1つずつ処理します。処理対象の地点を v とし、v に現在溜まっている水量を w リットルとします。

v にダムが設置されている場合：何もしません。w リットルの水はすべてそのまま v に残ります。
v にダムが設置されておらず、下流隣接地点が d 個（d \geq 1）存在する場合：v に溜まっている w リットルの水はすべて流れ出します。流れ出す水は d 個の下流隣接地点に均等に分配され、各下流隣接地点にそれぞれ \frac{w}{d} リットルの水が流れ込みます（下流隣接地点にダムが設置されていてもそこへ流れ込みます）。流出後、v の水量は 0 になります。
v にダムが設置されておらず、下流隣接地点が存在しない場合（水路が1本も接続されていない孤立した地点や、接続されたすべての地点の標高が v 以上である地点を含む）：水はそのまま v に残ります。

ある地点の流出処理で下流隣接地点に水が流入した場合、その水は即座にその地点に蓄積され、その地点自身が処理される際にまとめて扱われます。

すべての流出処理が完了した後、各地点に残っている水量を求めてください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
0 \leq K \leq N
1 \leq H_i \leq 10^9 （1 \leq i \leq N）
0 \leq W_i \leq 10^9 （1 \leq i \leq N）
1 \leq U_j < V_j \leq N （1 \leq j \leq M）
同じ地点の組を結ぶ水路は高々 1 本である（多重辺はない）
1 \leq S_k \leq N （1 \leq k \leq K）
S_1, S_2, \ldots, S_K はすべて異なる
入力はすべて整数で与えられる

入力

N M K
H_1 H_2 \ldots H_N
W_1 W_2 \ldots W_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
S_1 S_2 \ldots S_K

1 行目には、地点の数 N、水路の数 M、ダムが設置された地点の数 K が、スペース区切りで与えられる。
2 行目には、各地点の標高 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
3 行目には、各地点の初期水量 W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。
続く M 行にわたり、各水路の情報が与えられる。そのうち j 行目（入力全体の 3 + j 行目）には、j 番目の水路が結ぶ地点 U_j と V_j がスペース区切りで与えられる。
K \geq 1 の場合、最後の行にダムが設置された地点の番号 S_1, S_2, \ldots, S_K がスペース区切りで与えられる。K = 0 の場合、この行は存在しない。

出力

すべての流出処理が完了した後の各地点の水量を、地点 1 から地点 N の順にスペース区切りで 1 行で出力せよ。均等分配により水量が整数にならない場合があるため、小数で出力してもよい。出力の各値について、真の値との絶対誤差が 10^{-6} 以内、または真の値が 0 でないとき相対誤差が 10^{-6} 以内であれば正解とする。

入力例 1

出力例 1

0.0000000000 0.0000000000 8.0000000000 4.0000000000

入力例 2

出力例 2

0.0000000000 6.0000000000 0.0000000000

入力例 3

6 7 1
50 40 40 30 20 10
18 6 0 0 0 0
1 2
1 3
2 4
2 5
3 5
4 6
5 6
5

出力例 3

0.0000000000 0.0000000000 0.0000000000 0.0000000000 16.5000000000 7.5000000000

入力例 4

8 10 2
100 80 80 60 50 50 30 10
24 0 0 0 12 0 0 0
1 2
1 3
2 4
3 4
3 5
4 6
4 7
5 7
6 8
7 8
4 6

出力例 4

0.0000000000 0.0000000000 0.0000000000 18.0000000000 0.0000000000 0.0000000000 0.0000000000 18.0000000000

入力例 5

1 0 0
1000000000
999999999

出力例 5

999999999.0000000000

Score : 300 pts

Problem Statement

Takahashi is performing a terrain simulation of a mountainous area.

The mountainous area has N locations, each numbered from 1 to N. Location i has an elevation of H_i and initially holds W_i liters of rainwater.

The locations are connected by M channels. The j-th channel bidirectionally connects location U_j and location V_j. Water flows only from locations with higher elevation to locations with lower elevation. That is, if two locations connected by a channel have the same elevation, water does not flow through that channel.

For a location v, among the locations directly connected to v by a channel, those with elevation strictly lower than v are called the downstream neighbors of v.

Takahashi has installed dams at K locations (if K = 0, no dams are installed). The locations where dams are installed are numbered S_1, S_2, \ldots, S_K. At a location where a dam is installed, water may flow in from other locations through channels, but no water ever flows out from that location.

The water outflow from each location is processed according to the following procedure:

Sort all locations in decreasing order of elevation. Since water does not flow between locations of the same elevation, the ordering among locations with the same elevation is arbitrary (the result does not depend on the processing order).
Process each location one by one in this order. Let v be the location being processed, and let w liters be the amount of water currently accumulated at v.

If a dam is installed at v: Do nothing. All w liters of water remain at v.
If no dam is installed at v, and there are d downstream neighbors (d \geq 1): All w liters of water at v flow out. The outflowing water is distributed equally among the d downstream neighbors, with each downstream neighbor receiving \frac{w}{d} liters of water (water flows into a downstream neighbor even if a dam is installed there). After the outflow, the water amount at v becomes 0.
If no dam is installed at v, and there are no downstream neighbors (including isolated locations with no connected channels, or locations where all connected locations have elevation greater than or equal to v): The water remains at v as is.

When water flows into a downstream neighbor during the outflow processing of some location, that water is immediately accumulated at the downstream neighbor and is handled collectively when that downstream neighbor itself is processed.

After all outflow processing is complete, determine the amount of water remaining at each location.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
0 \leq K \leq N
1 \leq H_i \leq 10^9 (1 \leq i \leq N)
0 \leq W_i \leq 10^9 (1 \leq i \leq N)
1 \leq U_j < V_j \leq N (1 \leq j \leq M)
There is at most one channel connecting the same pair of locations (no multi-edges)
1 \leq S_k \leq N (1 \leq k \leq K)
S_1, S_2, \ldots, S_K are all distinct
All input values are integers

Input

N M K
H_1 H_2 \ldots H_N
W_1 W_2 \ldots W_N
U_1 V_1
U_2 V_2
\vdots
U_M V_M
S_1 S_2 \ldots S_K

The first line contains the number of locations N, the number of channels M, and the number of locations with dams K, separated by spaces.
The second line contains the elevations H_1, H_2, \ldots, H_N of each location, separated by spaces.
The third line contains the initial water amounts W_1, W_2, \ldots, W_N of each location, separated by spaces.
The following M lines contain the channel information. The j-th of these lines (line 3 + j of the entire input) contains the locations U_j and V_j connected by the j-th channel, separated by a space.
If K \geq 1, the last line contains the location numbers S_1, S_2, \ldots, S_K where dams are installed, separated by spaces. If K = 0, this line does not exist.

Output

Output the water amounts at each location after all outflow processing is complete, from location 1 to location N, separated by spaces on a single line. Since equal distribution may result in non-integer water amounts, decimal output is acceptable. For each output value, the answer is considered correct if the absolute error from the true value is at most 10^{-6}, or if the true value is non-zero and the relative error is at most 10^{-6}.

Sample Input 1

Sample Output 1

0.0000000000 0.0000000000 8.0000000000 4.0000000000

Sample Input 2

Sample Output 2

0.0000000000 6.0000000000 0.0000000000

Sample Input 3

6 7 1
50 40 40 30 20 10
18 6 0 0 0 0
1 2
1 3
2 4
2 5
3 5
4 6
5 6
5

Sample Output 3

0.0000000000 0.0000000000 0.0000000000 0.0000000000 16.5000000000 7.5000000000

Sample Input 4

8 10 2
100 80 80 60 50 50 30 10
24 0 0 0 12 0 0 0
1 2
1 3
2 4
3 4
3 5
4 6
4 7
5 7
6 8
7 8
4 6

Sample Output 4

0.0000000000 0.0000000000 0.0000000000 18.0000000000 0.0000000000 0.0000000000 0.0000000000 18.0000000000

Sample Input 5

1 0 0
1000000000
999999999

Sample Output 5

999999999.0000000000

C - ネットワークの通信コスト

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

配点 : 366 点

問題文

N 個の中継局からなるネットワークがあります。中継局には 1 から N までの番号が付いており、ネットワークは木構造をしています。具体的には、N - 1 本の回線があり、j 番目 (1 \leq j \leq N-1) の回線は中継局 U_j と中継局 V_j を双方向に結んでいます。

各中継局 i にはアンテナが設置されており、その基準座標は (X_i, Y_i) です。

各中継局 i は「通常モード」または「反転モード」のいずれかの動作モードを持ち、最初はすべての中継局が通常モードです。

中継局 i のアンテナの 実効座標 を次のように定めます。

通常モードのとき：実効座標は (X_i, Y_i)
反転モードのとき：実効座標は (-X_i, -Y_i)

隣接する中継局 u, v を結ぶ回線の 通信コスト は、それぞれの実効座標間のマンハッタン距離で定義されます。すなわち、中継局 u の実効座標を (X'_u, Y'_u)、中継局 v の実効座標を (X'_v, Y'_v) としたとき、通信コストは |X'_u - X'_v| + |Y'_u - Y'_v| です。

また、整数値の補正パラメータ S があり、初期値は 0 です。

高橋君は Q 個の操作を順に行います。操作は次の 3 種類です。

1 C : 中継局 C の動作モードを切り替える（通常モードなら反転モードに、反転モードなら通常モードにする）。
2 W : S に W を加算する。
3 A B : 中継局 A から中継局 B までの木上の唯一の単純パスについて、その時点での各中継局の動作モードおよび S の値を用いて以下の値を計算し、出力する。

\text{(パス上の各回線の通信コストの総和)} + S \times \text{(パス上の中継局の個数)}

ここで、パス上の中継局の個数は端点 A, B を含みます。特に A = B のとき、パス上の回線は 0 本、中継局は 1 個です。

なお、出力する値は負になることもあります。

制約

2 \leq N \leq 5000
1 \leq Q \leq 5000
-10^5 \leq X_i \leq 10^5
-10^5 \leq Y_i \leq 10^5
1 \leq U_j \leq N
1 \leq V_j \leq N
U_j \neq V_j
与えられるグラフは木である（連結で閉路を持たない）
種類 1 の操作について、1 \leq C \leq N
種類 2 の操作について、-10^5 \leq W \leq 10^5
種類 3 の操作について、1 \leq A \leq N, 1 \leq B \leq N（A = B の場合もある）
種類 3 の操作は 1 個以上存在する
入力はすべて整数

入力

N Q
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
query_1
query_2
\vdots
query_Q

1 行目には、中継局の数 N と操作の数 Q がスペース区切りで与えられる。
続く N 行のうち i 行目 (1 \leq i \leq N) には、中継局 i の基準座標 X_i, Y_i がスペース区切りで与えられる。
続く N - 1 行のうち j 行目 (1 \leq j \leq N-1) には、j 番目の回線が結ぶ 2 つの中継局の番号 U_j, V_j がスペース区切りで与えられる。
続く Q 行のうち k 行目 (1 \leq k \leq Q) には、k 番目の操作が与えられる。各操作は以下の形式で与えられる。
種類 1 の操作: 1 C
種類 2 の操作: 2 W
種類 3 の操作: 3 A B

出力

種類 3 の操作それぞれについて、答えを 1 行に 1 つずつ、操作が行われた順に出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

2 10
100000 -100000
-100000 100000
1 2
3 1 2
3 1 1
2 -100000
3 2 2
1 1
3 1 2
1 2
3 1 2
2 100000
3 2 1

出力例 5

Score : 366 pts

Problem Statement

There is a network consisting of N relay stations. The relay stations are numbered from 1 to N, and the network has a tree structure. Specifically, there are N - 1 links, and the j-th (1 \leq j \leq N-1) link bidirectionally connects relay station U_j and relay station V_j.

Each relay station i has an antenna installed, with base coordinates (X_i, Y_i).

Each relay station i has an operation mode of either "normal mode" or "inverted mode", and initially all relay stations are in normal mode.

The effective coordinates of relay station i's antenna are defined as follows:

In normal mode: the effective coordinates are (X_i, Y_i)
In inverted mode: the effective coordinates are (-X_i, -Y_i)

The communication cost of a link connecting adjacent relay stations u and v is defined as the Manhattan distance between their respective effective coordinates. That is, if the effective coordinates of relay station u are (X'_u, Y'_u) and the effective coordinates of relay station v are (X'_v, Y'_v), the communication cost is |X'_u - X'_v| + |Y'_u - Y'_v|.

Additionally, there is an integer-valued correction parameter S, with an initial value of 0.

Takahashi performs Q operations in order. There are 3 types of operations:

1 C : Toggle the operation mode of relay station C (switch from normal mode to inverted mode, or from inverted mode to normal mode).
2 W : Add W to S.
3 A B : For the unique simple path from relay station A to relay station B on the tree, compute and output the following value using the current operation modes of each relay station and the current value of S:

\text{(sum of communication costs of each link on the path)} + S \times \text{(number of relay stations on the path)}

Here, the number of relay stations on the path includes the endpoints A and B. In particular, when A = B, there are 0 links and 1 relay station on the path.

Note that the output value may be negative.

Constraints

2 \leq N \leq 5000
1 \leq Q \leq 5000
-10^5 \leq X_i \leq 10^5
-10^5 \leq Y_i \leq 10^5
1 \leq U_j \leq N
1 \leq V_j \leq N
U_j \neq V_j
The given graph is a tree (connected and has no cycles)
For type 1 operations, 1 \leq C \leq N
For type 2 operations, -10^5 \leq W \leq 10^5
For type 3 operations, 1 \leq A \leq N, 1 \leq B \leq N (the case A = B is possible)
There is at least 1 type 3 operation
All input values are integers

Input

N Q
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
query_1
query_2
\vdots
query_Q

The first line contains the number of relay stations N and the number of operations Q, separated by a space.
In the following N lines, the i-th line (1 \leq i \leq N) contains the base coordinates X_i, Y_i of relay station i, separated by a space.
In the following N - 1 lines, the j-th line (1 \leq j \leq N-1) contains the numbers U_j, V_j of the two relay stations connected by the j-th link, separated by a space.
In the following Q lines, the k-th line (1 \leq k \leq Q) contains the k-th operation. Each operation is given in the following format:
Type 1 operation: 1 C
Type 2 operation: 2 W
Type 3 operation: 3 A B

Output

For each type 3 operation, output the answer on a single line, in the order the operations are performed.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

2 10
100000 -100000
-100000 100000
1 2
3 1 2
3 1 1
2 -100000
3 2 2
1 1
3 1 2
1 2
3 1 2
2 100000
3 2 1

Sample Output 5

D - 山脈の眺望

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

配点 : 400 点

問題文

高橋君は山の写真を撮るのが趣味です。

高橋君の前には N 個の山が一列に並んでおり、山には 1 から N までの番号がついています。

i 番目の山の標高は A_i 、美しさは B_i です。

雲が高さ X で水平に広がっているとき、標高が X 以上である山（すなわち A_i \geq X を満たす山 i）だけが雲の上に顔を出し、高橋君から見えます。

高橋君は、見えている山の番号の集合を、番号が連続している極大な区間（これ以上両端を広げられない連続区間）に分割し、各区間を山脈として撮影します。

各山脈について、その山脈に含まれる山の美しさ B_i の最大値をその山脈の眺望値とします。

すべての山脈の眺望値の合計を、雲の高さ X における眺望値の総和と呼びます。

例えば、見えている山の番号が 2, 3, 4, 7, 8 である場合、山脈は \{2, 3, 4\} と \{7, 8\} の 2 つです。

眺望値の総和は \max(B_2, B_3, B_4) + \max(B_7, B_8) となります。

見えている山がひとつもない場合、眺望値の総和は 0 とします。

Q 個の質問が与えられます。

j 番目の質問では雲の高さ X_j が与えられるので、そのときの眺望値の総和を求めてください。

制約

1 \leq N
1 \leq Q
N + Q \leq 2 \times 10^5
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
1 \leq B_i \leq 10^9 (1 \leq i \leq N)
1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
入力はすべて整数である

入力

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
X_1
X_2
\vdots
X_Q

1 行目には、山の個数を表す N と、質問の個数を表す Q が、スペース区切りで与えられる。
続く N 行のうち i 行目には、i 番目の山の標高を表す A_i と、美しさを表す B_i が、スペース区切りで与えられる。
続く Q 行のうち j 行目には、j 番目の質問における雲の高さを表す X_j が与えられる。

出力

Q 行出力せよ。

j 行目には、雲の高さが X_j のときの眺望値の総和を出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

40 15
1 1000000000
1000000000 1
500000000 700
750000000 900
250000000 800
600000000 1200
600000000 1100
100 5000
999999999 300
400000000 400
800000000 2000
200000000 50
300000000 60
700000000 70
700000001 80
123456789 90
987654321 100
111111111 110
222222222 220
333333333 330
444444444 440
555555555 550
666666666 660
777777777 770
888888888 880
999999998 990
135791357 135
246802468 246
357913579 357
468024680 468
579135791 579
680246802 680
791357913 791
802468024 802
913579135 913
24 24
42 42
314159265 314
271828182 271
161803398 161
1
100
1000000000
999999999
800000000
700000000
600000000
500000000
400000000
300000000
200000000
123456789
50
100000001
900000000

出力例 4

入力例 5

1 1
1 1000000000
1000000000

出力例 5

Score : 400 pts

Problem Statement

Takahashi's hobby is taking photographs of mountains.

In front of Takahashi, there are N mountains lined up in a row, numbered from 1 to N.

The i-th mountain has an elevation of A_i and a beauty of B_i.

When clouds spread horizontally at height X, only mountains with elevation X or higher (i.e., mountains i satisfying A_i \geq X) appear above the clouds and are visible to Takahashi.

Takahashi divides the set of visible mountain numbers into maximal intervals of consecutive numbers (contiguous intervals that cannot be extended further on either end), and photographs each interval as a mountain range.

For each mountain range, the maximum beauty B_i among the mountains in that range is defined as the view value of that mountain range.

The sum of the view values of all mountain ranges is called the total view value at cloud height X.

For example, if the visible mountain numbers are 2, 3, 4, 7, 8, then there are 2 mountain ranges: \{2, 3, 4\} and \{7, 8\}.

The total view value is \max(B_2, B_3, B_4) + \max(B_7, B_8).

If no mountains are visible, the total view value is 0.

You are given Q queries.

In the j-th query, you are given the cloud height X_j. Determine the total view value at that time.

Constraints

1 \leq N
1 \leq Q
N + Q \leq 2 \times 10^5
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
1 \leq B_i \leq 10^9 (1 \leq i \leq N)
1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
All inputs are integers

Input

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
X_1
X_2
\vdots
X_Q

The first line contains N, the number of mountains, and Q, the number of queries, separated by a space.
The following N lines each contain, on the i-th line, the elevation A_i and beauty B_i of the i-th mountain, separated by a space.
The following Q lines each contain, on the j-th line, the cloud height X_j for the j-th query.

Output

Output Q lines.

On the j-th line, output the total view value when the cloud height is X_j.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

40 15
1 1000000000
1000000000 1
500000000 700
750000000 900
250000000 800
600000000 1200
600000000 1100
100 5000
999999999 300
400000000 400
800000000 2000
200000000 50
300000000 60
700000000 70
700000001 80
123456789 90
987654321 100
111111111 110
222222222 220
333333333 330
444444444 440
555555555 550
666666666 660
777777777 770
888888888 880
999999998 990
135791357 135
246802468 246
357913579 357
468024680 468
579135791 579
680246802 680
791357913 791
802468024 802
913579135 913
24 24
42 42
314159265 314
271828182 271
161803398 161
1
100
1000000000
999999999
800000000
700000000
600000000
500000000
400000000
300000000
200000000
123456789
50
100000001
900000000

Sample Output 4

Sample Input 5

1 1
1 1000000000
1000000000

Sample Output 5

E - 積み荷の安定配置

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

配点 : 466 点

問題文

高橋君は倉庫で荷物の管理を担当しています。倉庫には N 個の荷物が一列に並んでおり、左から順に荷物 1 、荷物 2 、...、荷物 N と番号がついています。

各荷物 i には重さがあり、その重さは整数 A_i で表されます。

高橋君は、連続した荷物をまとめて棚に積み上げる作業を行います。棚に積む荷物の区間 [l, r] が「安定配置」であるとは、以下の条件を満たすことを指します：

区間内の各荷物 j （ l < j \leq r ）について、 l \leq i < j かつ A_i \leq A_j となる荷物 i が少なくとも 1 つ存在する。

これは、各荷物が自分より左にある区間内のいずれかの荷物を支えとして安定して積めることを意味します。重さが同じか軽い荷物の上には、その荷物以上の重さの荷物を安定して積むことができます。最も左の荷物は棚の底に直接置くため、この条件の対象外です。

青木君は高橋君に Q 個の質問をしました。各質問では区間 [L_k, R_k] が与えられ、この区間に完全に含まれる連続部分区間のうち、安定配置となるものの個数を求めてください。

制約

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 10^5
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
1 \leq L_k \leq R_k \leq N (1 \leq k \leq Q)
入力はすべて整数

入力

N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

1 行目には、荷物の個数を表す N と、質問の個数を表す Q が、スペース区切りで与えられる。
2 行目には、各荷物の重さを表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
3 行目から Q 行にわたって、各質問の区間 [L_k, R_k] が与えられる。
2 + k 行目では、 k 番目の質問の左端 L_k と右端 R_k がスペース区切りで与えられる。

出力

Q 行出力してください。 k 行目には、 k 番目の質問に対する答え、すなわち区間 [L_k, R_k] に完全に含まれる連続部分区間のうち、安定配置となるものの個数を出力してください。

入力例 1

出力例 1

入力例 2

6 4
6 5 4 3 2 1
1 6
1 1
2 5
5 6

出力例 2

入力例 3

12 8
4 7 3 3 8 2 6 6 1 5 9 4
1 12
1 6
3 8
5 11
7 12
2 2
4 10
9 12

出力例 3

入力例 4

30 12
15 3 8 8 20 1 2 2 2 25 10 10 5 30 4 6 6 12 11 40 7 7 7 50 9 18 18 17 60 1
1 30
1 15
16 30
5 20
10 25
2 9
12 18
21 29
6 6
14 24
3 27
28 30

出力例 4

入力例 5

1 1
1000000000
1 1

出力例 5

Score : 466 pts

Problem Statement

Takahashi is in charge of managing packages in a warehouse. There are N packages lined up in a row in the warehouse, numbered from left to right as package 1, package 2, ..., package N.

Each package i has a weight represented by an integer A_i.

Takahashi performs the task of stacking consecutive packages onto a shelf. An interval [l, r] of packages to be placed on the shelf is called a "stable arrangement" if it satisfies the following condition:

For each package j in the interval (l < j \leq r), there exists at least one package i such that l \leq i < j and A_i \leq A_j.

This means that each package can be stably stacked using some package to its left within the interval as support. A package can be stably stacked on top of another package that has the same or lighter weight. The leftmost package is placed directly on the bottom of the shelf, so it is exempt from this condition.

Aoki asked Takahashi Q questions. For each question, an interval [L_k, R_k] is given. Find the number of contiguous subintervals completely contained within this interval that form a stable arrangement.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq Q \leq 10^5
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
1 \leq L_k \leq R_k \leq N (1 \leq k \leq Q)
All inputs are integers

Input

N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

The first line contains N, the number of packages, and Q, the number of questions, separated by a space.
The second line contains A_1, A_2, \ldots, A_N, the weights of each package, separated by spaces.
The following Q lines contain the interval [L_k, R_k] for each question.
The (2 + k)-th line contains the left endpoint L_k and right endpoint R_k of the k-th question, separated by a space.

Output

Print Q lines. On the k-th line, print the answer to the k-th question, that is, the number of contiguous subintervals completely contained within the interval [L_k, R_k] that form a stable arrangement.

Sample Input 1

Sample Output 1

Sample Input 2

6 4
6 5 4 3 2 1
1 6
1 1
2 5
5 6

Sample Output 2

Sample Input 3

12 8
4 7 3 3 8 2 6 6 1 5 9 4
1 12
1 6
3 8
5 11
7 12
2 2
4 10
9 12

Sample Output 3

Sample Input 4

30 12
15 3 8 8 20 1 2 2 2 25 10 10 5 30 4 6 6 12 11 40 7 7 7 50 9 18 18 17 60 1
1 30
1 15
16 30
5 20
10 25
2 9
12 18
21 29
6 6
14 24
3 27
28 30

Sample Output 4

Sample Input 5

1 1
1000000000
1 1