题目
农夫约翰有一块很大的田，他正在考虑种甜玉米。经过对他农田的调查，FJ发现它形成了一个（N-1）×（N-1）的
正方形。西南角为坐标（0,0），东北角是（N-1，N-1）。在某些整数坐标的位置中有双头喷头，每一个都能够同
时喷洒水和肥料。一个在（i，j）处的双头喷头会将水洒在农田中所有在其东面且在其北面的区域，将肥料洒在农
田中所有在其南面且在其西面的区域。形式化地说，这个喷头将会将水洒在所有满足N≥x≥i和N≥y≥j的实数坐标
(x,y)上，会将肥料洒在所有满足0≤x≤i和0≤y≤j的实数坐标上农民约翰想在一些边与坐标轴平行的长方形农田
里种植甜玉米。然而，为了甜玉米的生长，矩形内的所有点都必须由双头喷头浇水和施肥。当然，矩形必须有正的
面积，否则农民约翰就不能在里面种植任何玉米！帮助农民约翰确定可以种植甜玉米的拥有正面积的矩形农田数。
由于这个数字可能很大，所以输出对为10^9 + 7取模
题解
数论题，主要就是化简算式
假设该农田在第一象限上
设\(up_i\)是第\(i\)行向右能种植到的最大值，\(lw_i\)是第\(i\)行向左能种植到的最小值，\(l_k\)是第\(i\)列向下能种植到的最小值
其中\(up\),\(lw\),\(l\)都可以在\(O(n)\)时间内预处理出来
由于最后的合法范围是阶梯状的
所以答案为
但这是\(O(N^3)\)的，所以考虑化简
先把最后的\(\sum\limits_{k=lw_i}^{k=j-1} i-l_k\)拆开，原式变成
然后提出\(i\)变成
高斯公式求和化简中间的\(\sum\limits_{j=lw_i+1}^{j=up_i}(j-lw_i)\)变成
至此，前面的\(\sum\limits_{i=0}^{i=n-1}i*\frac{(1+up_i-lw_i)*(up_i-lw_i)}{2}\)已经可以\(O(n)\)求出
所以我们接下来只需考虑后面的\({\sum\limits_{j=lw_i+1}^{j=up_i}\sum\limits_{k=lw_i}^{k=j-1}l_k}\)
设\(s\)为\(l\)的前缀和
那么就可以将后面的部分化简为
设\(pr\)为\(s\)的前缀和，则
然后这个式子也可以在\(O(N)\)的时间内求出来了
最后的结果为
\(Code\)
#include<bits/stdc++.h>
#define sco 1000010
#define mod 1000000007
#define ll long long
using namespace std;
ll n,ans,anss,lw[sco],up[sco],l[sco],s[sco],pr[sco];
ll read(){
ll x=0,w=1;
char ch;
while((ch=getchar())>'9' || ch<'0'){if(ch=='-')w=-1;}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*w;
}
ll ksm(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=1ll*res*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return res;
}
int main(){
n=read();
for(ll i=0;i<n;++i){
up[i]=0;lw[i]=10000000;
}
for(ll i=1;i<=n;++i){
ll x,y;
x=read();y=read();
up[y]=lw[y]=x;
l[x]=y;
}
for(ll i=n-2;i>=0;--i){
up[i]=max(up[i+1],up[i]);
}
for(ll i=1;i<n;++i){
lw[i]=min(lw[i-1],lw[i]);
l[i]=min(l[i],l[i-1]);
}
for(ll i=0;i<n;++i){
ans=(ans+1ll*i*(1+up[i]-lw[i])*(up[i]-lw[i]))%mod;
}
ans=1ll*ans*ksm(2,mod-2)%mod;
pr[0]=s[0]=l[0];
for(ll i=1;i<n;++i){
s[i]=(s[i-1]+l[i])%mod;
pr[i]=(pr[i-1]+s[i])%mod;
}
for(ll i=0;i<n;++i){
anss=(anss+pr[up[i]-1])%mod;
anss=(anss+mod-pr[lw[i]-1])%mod;
anss=(anss+mod-(s[lw[i]-1]*(up[i]-lw[i])%mod))%mod;
}
printf("%lld",(ans-anss+mod)%mod);
return 0;
}