← 返回题目列表

AtCoder · arc179_e

E. 矩形串联

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

对于正整数 h 和 w,让 (h,w) 表示一个矩形,高度 h 和宽度 w。在这个问题中,我们不考虑旋转矩形,并且矩形 (h,w) 和 (w,h) 区分时 h \neq w.

一系列矩形 ((h_1,w_1),(h_2,w_2),\dots ,(h_n,w_n)) 被称为 矩形生成序列 如果存在成功执行以下步骤的方法:

  • 让矩形 X be (h_1,w_1)。今后,让 H 和 W 分别表示矩形的高度和宽度 X 在每一步。
  • 对于 i=2,3,\dots ,n,执行以下操作之一。如果两者都不能执行,则该过程不成功地终止。
    • 如果高度 X 等于 h_i,附加矩形 (h_i,w_i) 水平到 X。正式来说,如果 H=h_i 当时,更换 X 与矩形 (H,W+w_i).
    • 如果宽度 X 等于 w_i,附加矩形 (h_i,w_i) 垂直于 X。正式来说,如果 W=w_i 当时,更换 X 与矩形 (H+h_i,W).
  • 如果上述一系列操作没有失败,则过程成功终止。

你被给予 N 矩形。的 i第一个矩形的高度为 H_i 和宽度 W_i.

查找正整数对的数量 (l,r) 满足 1 \le l \le r \le N 以及以下条件:

  • 矩形序列 ((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);有七个。

例如,对于 (l,r)=(2,4),如果第一个附件是垂直完成的,第二个附件是水平完成的,则过程成功。


示例输入 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