2709. [Codeforces 526 F]Pudding Monsters

【题目描述】

翻译：Mike    原题链接

在这个问题中，你将接触到简化版的布丁妖怪游戏。

制作游戏的一个重要过程就是划分等级。布丁妖怪游戏的场地是一个n*n的网格，其中n个格子里有妖怪，另一些格子中有游戏道具。这个游戏就是移动妖怪，当两个妖怪相互接触时，他们会粘在一起并变成一个更大的妖怪。（别忘了他们原先是布丁）

数据显示最有意思的地图就是开始时每行每列都有一个妖怪，剩余的格子填满了其他游戏道具。

一个被广泛使用的开发游戏的途径就是节省空余的资源。例如，如果有一个n*n的大地图，你可以从中抽取一个k*k的小地图，其中恰好含有k个妖怪，并将其作为原地图的简化版。

你想知道在初始地图中有多少个k*k的小地图，其中恰好含有k个布丁妖怪，请输出方案数。

【输入格式】

第一行一个整数n(1<=n<=300,000)，表示地图的行和列。

接下来n行，第i行有两个整数ri,ci(1<=ri,ci<=n)，表示第i个布丁妖怪所在的行和列。

输入数据保证ri互不相同，且ci互不相同。

【输出格式】

输出初始地图中有多少个正方形能形成新的地图。

【样例输入】

5
1 1
4 3
3 2
2 4
5 5

【样例输出】

10

【来源】

Codeforces 526 F