#P5187. [Usaco2018 Jan]Sprinklers

    ID: 2254 传统题 1000ms 128MiB 尝试: 44 已通过: 27 难度: 8 上传者: 标签>难度分类提高+/省选-排序与序列处理前后缀最值组合数学贡献法一维前缀和线性代数与代数等差数列求和CF2400Platinum

[Usaco2018 Jan]Sprinklers

[USACO18JAN] Sprinklers P

题面翻译

农夫约翰有一块边长为 N−1N-1 的正方形田地,西南角为 (0,0)(0,0),东北角为 (N−1,N−1)(N-1,N-1)。

在一些整数坐标处有双头喷头。位于 (i,j)(i,j) 的喷头给其东北方向的区域浇水,给其西南方向的区域施肥:

  • 水覆盖满足 N≥x≥iN\ge x\ge i 且 N≥y≥jN\ge y\ge j 的实数坐标 (x,y)(x,y);
  • 肥料覆盖满足 0≤x≤i0\le x\le i 且 0≤y≤j0\le y\le j 的实数坐标 (x,y)(x,y)。

农夫想选择田地内一个边平行于坐标轴、四个顶点都是整数坐标、面积为正的矩形,要求其中每个点都同时被浇水和施肥。求这样的矩形数量,答案对 109+710^9+7 取模。

输入格式

从标准输入读入。第一行一个整数 NN(1≤N≤1051\le N\le10^5)。接下来 NN 行,每行两个整数 i,ji,j(0≤i,j≤N−10\le i,j\le N-1),表示一个喷头的位置。每个横坐标、每个纵坐标都恰好出现一次。

输出格式

向标准输出写出一行一个整数,表示答案模 109+710^9+7 的余数。

题目描述

Farmer John has a large field, and he is thinking of planting sweet corn in some part of it. After surveying his field, FJ found that it forms an (N−1)×(N−1)(N-1) \times (N-1) square. The southwest corner is at coordinates (0,0)(0,0), and the northeast corner is at (N−1,N−1)(N-1,N-1).

At some integer coordinates there are double-headed sprinklers, each one sprinkling both water and fertilizer. A double-heading sprinkler at coordinates (i,j)(i,j) sprinkles water on the part of the field north and east of it, and sprinkles fertilizer on the part of the field south and west of it. Formally, it waters all real coordinates (x,y)(x,y) for which N≥x≥iN \geq x \geq i and N≥y≥jN \geq y \geq j, and it fertilizes all real coordinates (x,y)(x,y) for which 0≤x≤i0 \leq x \leq i and 0≤y≤j0 \leq y \leq j.

Farmer John wants to plant sweet corn in some axis-aligned rectangle in his field with integer-valued corner coordinates. However, for the sweet corn to grow, all points in the rectangle must be both watered and fertilized by the double-headed sprinklers. And of course the rectangle must have positive area, or Farmer John wouldn't be able to grow any corn in it!

Help Farmer John determine the number of rectangles of positive area in which he could grow sweet corn. Since this number may be large, output the remainder of this number modulo 109+710^9 + 7.

输入格式

The first line of the input consists of a single integer NN, the size of the field (1≤N≤1051 \leq N \leq 10^5).

The next NN lines each contain two space-separated integers. If these integers are ii and jj, where 0≤i,j≤N−10 \leq i,j \leq N-1, they denote a sprinkler located at (i,j)(i,j).

It is guaranteed that there is exactly one sprinkler in each column and exactly one sprinkler in each row. That is, no two sprinklers have the same xx-coordinate, and no two sprinklers have the same yy-coordinate.

输出格式

The output should consist of a single integer: the number of rectangles of positive area which are fully watered and fully fertilized, modulo 109+710^9 + 7.

样例 #1

样例输入 #1

5
0 4
1 1
2 2
3 0
4 3

样例输出 #1

21