【USACO 2018 January Platinum】Problem 3. Sprinklers

Description
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) square. The southwest corner is at coordinates (0,0), and the northeast corner is at (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) 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) for which N≥x≥i and N≥y≥j, and it fertilizes all real coordinates (x,y) for which 0≤x≤i and 0≤y≤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 10^9+7.
Input
The first line of the input consists of a single integer N, the size of the field (1≤N≤10^5).
The next N lines each contain two space-separated integers. If these integers are i and j, where 0≤i,j≤N−1, they denote a sprinkler located at (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 x-coordinate, and no two sprinklers have the same y-coordinate.
5
0 4
1 1
2 2
3 0
4 3
Output
21
The output should consist of a single integer: the number of rectangles of positive area which are fully watered and fully fertilized, modulo 10^9+7.

解法：
固定洒水的坐标后，能同时被施肥的格子呈现一个倒阶梯
由于每个坐标的横纵坐标不同，考虑对于每一个倒阶梯求上界刚好和阶梯上界重合的矩形，全部加在一起就是ans了。
最后维护点东东，就是O(n)了（是数据水还是方法妙？
注（从上到下枚举洒水的点
维护倒阶梯求上界刚好和阶梯上界重合的矩形其实只需维护三个东东
（1）sum表示阶梯中格子的总数，因为如果阶梯新加进一列，那一列一定是最长的，以那一列的最上面的格子作为左上角，阶梯中任意一个点可作为右下角
（2）z表示倒阶梯最上面那行的格子数，因为每次枚举到下一行时，倒阶梯最上面那行都要被删掉（我的code中用了一个单调栈维护，其实一个指针应该也足够了，不过我懒得改了
（3）当前阶梯中要被算的矩形的总数

code

#include<iostream>
#include<cstdio>
using namespace std;
int p=1000000007,n,hds[200001],sdh[200001];
int zha[200001],top=0,last=0;
long long ans=0,ans1=0,sum=0;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        hds[x]=y;sdh[y]=x;
    }
    int z=n-1;
    for(int i=0;i<n;i++){
        ans1-=(long long)(last-top)*(last-top+1)/2%p;
        sum=sum-last+top;
        while(top<last&&zha[top+1]<=i)top++;
        while(z>hds[i]){
            if(max(sdh[z],zha[last-1])>i){
                ++last;
                zha[last]=max(sdh[z],zha[last-1]);
                sum+=zha[last]-i;
                ans1+=sum;
            }z--;
        }ans1%=p;if(ans1<0)ans1+=p;
        ans+=ans1;ans%=p;
    }
    printf("%lld",ans);
    return 0;
}

【USACO 2018 January Platinum】Problem 3. Sprinklers

原文：https://www.cnblogs.com/believehopexm/p/12828732.html