分数: 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