题解

#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;
}