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 翻译