E - Rectangle Concatenation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

正整数 h,w に対し, 縦の辺の長さが h, 横の辺の長さが w であるような長方形を (h,w) と表すことにします. なお, 本問では長方形を回転する操作は考えず, h\neq w のとき長方形 (h,w) と長方形 (w,h) は異なるものとして扱います.

長方形の列 ((h_1,w_1),(h_2,w_2),\dots ,(h_n,w_n)) が 長方形生成列 であるとは, 次の手順が成功するような方法が存在することを言います.

  • 長方形 X を (h_1,w_1) とする. 以下では, 各時点での長方形 X の縦の辺の長さと横の辺の長さをそれぞれ H,W と表す.
  • i=2,3,\dots ,n の順に次のいずれか一方の操作を行う. いずれも行うことができないとき手順は失敗とし, 手順を終了する.
    • X の縦の辺の長さが h_i に等しいとき, X に長方形 (h_i,w_i) を横向きに結合する. 正確には, その時点で H=h_i のとき X を長方形 (H,W+w_i) に置き換える.
    • X の横の辺の長さが w_i に等しいとき, X に長方形 (h_i,w_i) を縦向きに結合する. 正確には, その時点で W=w_i のとき X を長方形 (H+h_i,W) に置き換える.
  • 上記の一連の操作が失敗しなかった場合は手順は成功とし, 手順を終了する.

N 個の長方形が与えられます. i 番目の長方形は, 縦の辺の長さが H_i, 横の辺の長さが W_i の長方形です.

1\le l\le r\le N を満たす正整数の組 (l,r) であって次の条件を満たすものの個数を求めてください.

  • 長方形の列 ((H_l,W_l),(H_{l+1},W_{l+1}),\dots ,(H_r,W_r)) が長方形生成列である.

制約

  • 1\leq N\leq 3\times 10^5
  • 1 \leq H_i,W_i \leq 10^6
  • 入力される値はすべて整数.

入力

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

N
H_1 W_1
H_2 W_2
\vdots
H_N W_N

出力

答えを出力せよ.

入力例 1

4
1 2
1 3
2 3
3 1

出力例 1

7

条件を満たす (l,r) は (1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(4,4) の 7 つです.

例えば, (l,r)=(2,4) については, 結合を縦向き \to 横向きの順に行うと手順が成功します.

入力例 2

5
2 1
2 1
1 2
3 2
1 4

出力例 2

10

入力例 3

1
1000000 1000000

出力例 3

1

入力例 4

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

出力例 4

55

Score : 800 points

Problem Statement

For positive integers h and w, let (h,w) denote a rectangle with height h and width w. In this problem, we do not consider rotating the rectangles, and the rectangles (h,w) and (w,h) are distinguished when h \neq w.

A sequence of rectangles ((h_1,w_1),(h_2,w_2),\dots ,(h_n,w_n)) is called a rectangle generation sequence if there exists a method that successfully follows the steps below:

  • Let the rectangle X be (h_1,w_1). Hereafter, let H and W respectively denote the height and width of the rectangle X at each step.
  • For i=2,3,\dots ,n, perform one of the following operations. If neither can be performed, the procedure unsuccessfully terminates.
    • If the height of X is equal to h_i, attach the rectangle (h_i,w_i) horizontally to X. Formally, if H=h_i at that time, replace X with the rectangle (H,W+w_i).
    • If the width of X is equal to w_i, attach the rectangle (h_i,w_i) vertically to X. Formally, if W=w_i at that time, replace X with the rectangle (H+h_i,W).
  • If the above series of operations does not fail, the procedure successfully terminates.

You are given N rectangles. The i-th rectangle has a height of H_i and a width of W_i.

Find the number of pairs of positive integers (l,r) that satisfy 1 \le l \le r \le N and the following condition:

  • The sequence of rectangles ((H_l,W_l),(H_{l+1},W_{l+1}),\dots ,(H_r,W_r)) is a rectangle generation sequence.

Constraints

  • 1 \leq N \leq 3 \times 10^5
  • 1 \leq H_i, W_i \leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
H_1 W_1
H_2 W_2
\vdots
H_N W_N

Output

Print the answer.

Sample Input 1

4
1 2
1 3
2 3
3 1

Sample Output 1

7

The pairs (l,r) that satisfy the condition are (1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(4,4); there are seven.

For example, for (l,r)=(2,4), the procedure succeeds if the first attachment is done vertically and the second is done horizontally.

Sample Input 2

5
2 1
2 1
1 2
3 2
1 4

Sample Output 2

10

Sample Input 3

1
1000000 1000000

Sample Output 3

1

Sample Input 4

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1

Sample Output 4

55