C++14(g++5.4) 解法, 执行用时: 42ms, 内存消耗: 3964K, 提交时间: 2020-03-25 15:08:05

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod = 1e9 + 7;
const int maxn = 100100;

int sl[maxn], sr[maxn], l[maxn], r[maxn];

int main() {
    int n;
    scanf("%d", &n);
    sl[0] = 1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &l[i], &r[i]);
        sl[i] = sl[i - 1] * 1ll * (r[i] - l[i] + 1) % mod;
    }
    sr[n + 1] = 1;
    for (int i = n; i >= 1; --i) {
        sr[i] = sr[i + 1] * 1ll * (r[i] - l[i] + 1) % mod;
    }
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        int tmp = 0;
        if (r[i] > r[i + 1]) {
            int L = max(l[i], r[i + 1] + 1), R = r[i];
            tmp = (R - L + 1) * 1ll * (r[i + 1] - l[i + 1] + 1) % mod;
        }
        if (r[i] >= l[i + 1]) {
             int L = max(l[i], l[i + 1]), R = min(r[i], r[i + 1]);
            if (L <= R) {
                tmp = (tmp + (R - l[i + 1] + L - l[i + 1]) * 1ll * (R - L + 1) / 2ll % mod) % mod;
            }
        }
        ans = (ans + sl[i - 1] * 1ll * sr[i + 2] % mod * 1ll * tmp % mod) % mod;
    }
    cout << (ans + sl[n]) % mod;
}

C++11(clang++ 3.9) 解法, 执行用时: 53ms, 内存消耗: 6360K, 提交时间: 2020-03-26 14:35:47

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
const int mod=1e9+7;
ll l[maxn],r[maxn],sz[maxn];
ll dp[maxn],sum[maxn];
ll qp(ll k,ll x){
	ll res=1;while(x){
		if(x&1) res=res*k%mod;k=k*k%mod;x>>=1;
	}return res;
}ll inv(ll x){
	return qp(x,mod-2);
}
int main(){
    int n;scanf("%d",&n);ll inv2=inv(2);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&l[i],&r[i]),sz[i]=r[i]-l[i]+1;
    sum[0]=1;sum[1]=dp[1]=r[1]-l[1]+1;
    for(int i=2;i<=n;i++){ ll res;
        dp[i]=dp[i-1]*sz[i]%mod;sum[i]=sum[i-1]*sz[i]%mod;
        if(r[i]<r[i-1]){
        	if(r[i]<l[i-1]) res=sz[i]*sz[i-1]%mod;
        	else{ ll k=r[i]-max(l[i-1]-1,l[i])+1;
        		res=((r[i-1]-r[i]-1)*sz[i]%mod+(sz[i]*2-k+1)%mod*k%mod*inv(2)%mod)%mod;
			}
		}else{
			if(l[i]>=r[i-1]) res=0;
			else{ ll k=r[i-1]-max(l[i-1]-1,l[i]),s=r[i-1]-l[i];
        		res=(s*2-k+1)%mod*k%mod*inv(2)%mod;
			}
		}dp[i]=(dp[i]+res*sum[i-2]%mod)%mod;
    }printf("%lld\n",dp[n]);
}