AT_arc179_e.[ARC179E] Rectangle Concatenation

对于正整数 $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$，则将长方形 $(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$。

请计算满足 $1\leq l\leq r\leq N$，且长方形序列 $((H_l,W_l),(H_{l+1},W_{l+1}),\dots,(H_r,W_r))$ 是长方形生成列的整数对 $(l,r)$ 的个数。

输入按以下格式从标准输入读入：

$N$
$H_1$ $W_1$
$H_2$ $W_2$
$\vdots$
$H_N$ $W_N$

输出答案。

数据范围

• $1\leq N\leq 3\times 10^5$
• $1\leq H_i,W_i\leq 10^6$
• 输入的所有值均为整数。

样例解释 1

满足条件的 $(l,r)$ 有 $7$ 个，分别为 $(1,1),(1,2),(2,2),(2,3),(2,4),(3,3),(4,4)$。例如，对于 $(l,r)=(2,4)$，若依次进行纵向拼接 $\to$ 横向拼接，则操作可以成功。

由 ChatGPT 4.1 翻译