AT_arc179_e [ARC179E] Rectangle Concatenation

[problemUrl]: https://atcoder.jp/contests/arc179/tasks/arc179_e 正整数 $ 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)) $ が長方形生成列である.

N/A

N/A

### 制約 - $ 1\leq\ N\leq\ 3\times\ 10^5 $ - $ 1\ \leq\ H_i,W_i\ \leq\ 10^6 $ - 入力される値はすべて整数. ### Sample Explanation 1 条件を満たす $ (l,r) $ は $ (1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(4,4) $ の $ 7 $ つです. 例えば, $ (l,r)=(2,4) $ については, 結合を縦向き $ \to $ 横向きの順に行うと手順が成功します.