Sprinklers

题目描述

农夫约翰有一大片田地，正在考虑在其中一部分种植甜玉米。经过测量，他发现田地构成一个 $(N-1) \times (N-1)$ 的正方形。西南角坐标为 $(0,0)$，东北角坐标为 $(N-1,N-1)$。

在一些整数坐标处有双向喷头，每个喷头同时喷洒水和肥料。位于 $(i,j)$ 的双向喷头会对其北侧和东侧的田地喷洒水，并对其南侧和西侧的田地施加肥料。形式化地说，它给所有满足 $N \geq x \geq i$ 且 $N \geq y \geq j$ 的实数坐标 $(x,y)$ 浇水，并给所有满足 $0 \leq x \leq i$ 且 $0 \leq y \leq j$ 的实数坐标 $(x,y)$ 施肥。

农夫约翰想在田地中选择一个与坐标轴对齐、四个角坐标均为整数的矩形来种植甜玉米。然而，为了让甜玉米生长，矩形内的所有点都必须同时被这些双向喷头浇水并施肥。当然，该矩形必须具有正面积，否则农夫约翰无法在其中种出任何玉米！

请帮助农夫约翰确定：他可以种植甜玉米的正面积矩形有多少个。由于答案可能很大，请输出该数量对 $10^9 + 7$ 取模后的结果。

输入格式

第一行输入一个整数 $N$，表示田地的大小（$1 \leq N \leq 10^5$）。 接下来 $N$ 行每行包含两个用空格分隔的整数。若这两个整数为 $i$ 和 $j$（$0 \leq i,j \leq N-1$），则表示在 $(i,j)$ 位置有一个喷头。 保证每一列恰好有一个喷头且每一行恰好有一个喷头。也就是说，任意两个喷头不会有相同的 $x$ 坐标，也不会有相同的 $y$ 坐标。

输出格式

输出一个整数：完全被浇水且完全被施肥的正面积矩形数量，对 $10^9 + 7$ 取模。

5
0 4
1 1
2 2
3 0
4 3

21

提示

题目来源：Dhruv Rohatgi

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum