C++14(g++5.4) 解法, 执行用时: 536ms, 内存消耗: 56676K, 提交时间: 2019-07-22 11:01:35

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int M = 20000005;
const int N = 1000005;
int n,l[N],r[N],ll[N],rr[N],s,sum,f[M];
LL ans;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d %d",&l[i],&r[i]);
    l[0]=r[0]=-1; l[n+1]=r[n+1]=1000000000;
    for (int i=1;i<=n;i++)
    {
        s+=r[i]-l[i]+1;
        rr[i]=min(s,l[i+1]-r[i]-1);
        s-=l[i+1]-r[i]-1;
        if (s<0) s=0;
    }
    s=0;
    for (int i=n;i>=1;i--)
    {
        s+=r[i]-l[i]+1;
        ll[i]=min(s,l[i]-r[i-1]-1);
        s-=l[i]-r[i-1]-1;
        if (s<0) s=0;
    }
    s=10000000; f[s]=1;
    for (int i=1;i<=n;i++)
    {
        for (int j=max(r[i-1]+rr[i-1]+1,l[i]-ll[i]);j<=r[i]+rr[i];ans+=sum,j++)
        if (j>=l[i] && j<=r[i]) sum+=f[s],f[++s]++; else sum-=f[--s],f[s]++;
    }
    printf("%lld\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 547ms, 内存消耗: 74604K, 提交时间: 2019-07-24 19:35:30

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define N 1000010
#define M 40000010
int l[N],r[N],n;
int L[N],R[N];
int num[M];
int main(){
	int i,j;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
	l[0]=r[0]=L[0]=R[0]=-1,l[n+1]=r[n+1]=1e9;
	int len=0;
	for(i=1;i<=n;i++){
		len+=r[i]-l[i]+1;
		R[i]=min(r[i]+len,l[i+1]-1);
		len-=l[i+1]-r[i]-1;
		if(len<0)len=0;
	}
	len=0;
	for(i=n;i;i--){
		len+=r[i]-l[i]+1;
		L[i]=max(l[i]-len,r[i-1]+1);
		len-=l[i]-r[i-1]-1;
		if(len<0)len=0;
	}
	int now=20000001;
	ll sum=0,ans=0;
	num[now]=1;//change
	for(i=1;i<=n;i++){
		for(j=max(L[i],R[i-1]+1);j<=R[i];j++){
			if(j>=l[i]&&j<=r[i]){
				sum+=num[now];
				num[++now]++;
			}else{
				sum-=num[--now];
				num[now]++;
			}
			ans+=sum;
		}
	}
	printf("%lld",ans);
	return 0;
}