CF526F Pudding Monsters

在本题中，你将遇到游戏 Pudding Monsters 的简化模型。 开发任何游戏的重要过程是创建关卡。Pudding Monsters 的游戏场地是一个 $n \times n$ 的矩形网格，其中 $n$ 个格子中各有一个怪物，其它部分可能包含游戏物体。玩法是将怪物在场地上移动。当两个怪物接触时，它们会粘在一起变成一个“大怪物”（记住，它们是布丁做的）。 统计显示，最有趣的地图在于：初始状态下，每一行和每一列恰好有一个怪物，其余地图细节则由合理布置其它游戏物体完成。 一种被广泛应用以提高开发效率的技巧是复用已有的资源。例如，当你有一个较大的 $n \times n$ 地图时，可以选择其中某个 $k \times k$ 的正方形区域，使其恰好包含 $k$ 个怪物，将其作为原地图的简化版本。 你想知道在初始地图中，有多少种方式可以选择一个恰好包含 $k$ 个布丁怪物的 $k \times k$ 正方形区域（$1 \leq k \leq n$）。请计算这样的不同区域的数目。

第一行包含一个整数 $n$（$1 \leq n \leq 3 \times 10^{5}$），表示初始场地的大小。 接下来的 $n$ 行，每行包含两个整数 $r_i, c_i$（$1 \leq r_i, c_i \leq n$），表示第 $i$ 个怪物所在位置的行号和列号。 保证所有 $r_i$ 各不相同，所有 $c_i$ 也各不相同。

输出能够构成新地图的不同正方形区域的数量。

由 ChatGPT 5 翻译