Description
Data Constraint
对于20%的数据，n<=6,0<=li<=ri<=15
对于40%的数据，n<=10,0<=li<=ri<=20
对于60%的数据，0<=li<=ri<=1000
对于100%的数据，n<=10^5,0<=li<=ri<=10^9,0<=si<=10^9
Solution
我们发现pi就是期望有多少人排在i之前，对于< i的点的区间[l,r]，他对i即其之后的点j在选[0,l-1]是没有贡献的，而对[l,r]的贡献是一个初始值为1，公差为1的等差数列/(rj-lj+1)/(ri-li+1)，而对[r+1,+∞]的贡献是一个初始值为r-l+1，公差为0的等差数列/(rj-lj+1)。那么那照这个思路正着做一次倒着做一次，用线段树维护每个点的期望值，即可算出答案。时间复杂度O(NlogN)。
Code
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const ll maxn=1e5+5,mo=1e9+7,ni=5e8+4;
struct code{
ll l,r;
ll sum,bz,bz1;
}f[maxn*100];
ll l[maxn],r[maxn],s[maxn],p[maxn],q[maxn],h[maxn];
ll n,i,t,j,k,num,ans,x,y,z,ans1;
void make(ll v,ll l,ll mid,ll r){
if (!f[v].l)f[f[v].l=++num]={0,0,0,0,0};if (!f[v].r)f[f[v].r=++num]={0,0,0,0,0};
ll z=f[v].bz,k=f[v].bz1,x=f[v].l,y=f[v].r;
f[x].sum=(f[x].sum+k*(mid-l+1)%mo*(mid-l)%mo*ni%mo+z*(mid-l+1)%mo)%mo;
f[y].sum=(f[y].sum+k*(r-mid)%mo*(r-mid-1)%mo*ni%mo+(z+k*(mid-l+1))%mo*(r-mid)%mo)%mo;
f[x].bz=(f[x].bz+z)%mo;f[x].bz1=(f[x].bz1+k)%mo;f[y].bz=(f[y].bz+z+k*(mid-l+1)%mo)%mo;f[y].bz1=(f[y].bz1+k)%mo;
f[v].bz=f[v].bz1=0;
}
void insert(ll l,ll r,ll &v,ll x,ll y,ll z){
ll mid=(l+r)/2;
if (!v) v=++num,f[v]={0,0,0,0,0};
if (f[v].bz && l!=r) make(v,l,mid,r);
if (l>=x && r<=y){
f[v].sum=((f[v].sum+k*(1+r-l)%mo*(r-l)%mo*ni%mo)%mo+z*(r-l+1)%mo)%mo;
f[v].bz=z;f[v].bz1=k;
return;
}
if (l<=y && mid>=x) insert(l,mid,f[v].l,x,y,z);
if (mid<y && r>=x) insert(mid+1,r,f[v].r,x,y,(z+k*max((ll)0,mid+1-max(x,l)))%mo);
f[v].sum=(f[f[v].l].sum+f[f[v].r].sum)%mo;
}
void find(ll l,ll r,ll v,ll x,ll y){
ll mid=(l+r)/2;
if (!v) return;
if (f[v].bz && l!=r) make(v,l,mid,r);
if (l>=x && r<=y){
t=(t+f[v].sum)%mo;
return;
}
if (l<=y && mid>=x) find(l,mid,f[v].l,x,y);
if (mid<y && r>=x) find(mid+1,r,f[v].r,x,y);
}
ll mi(ll x,ll y){
if (y==1) return x;
ll t=mi(x,y/2);
if (y%2) return t*t%mo*x%mo;return t*t%mo;
}
int main(){
freopen("sort.in","r",stdin);freopen("sort.out","w",stdout);
scanf("%lld",&n);num=1;p[0]=1;
for (i=1;i<=n;i++)
scanf("%lld%lld%lld",&s[i],&l[i],&r[i]),p[i]=p[i-1]*(r[i]-l[i]+1)%mo,h[i]=mi(r[i]-l[i]+1,mo-2);
q[n+1]=1;
for (i=n;i>=1;i--)
q[i]=q[i+1]*(r[i]-l[i]+1)%mo;
for (i=1;i<=n;i++){
t=0;
find(0,mo,1,l[i],r[i]);t%=mo;
ans=(ans+t*s[i]%mo*h[i]%mo)%mo;k=p[i-1]*q[i+1]%mo,
insert(0,mo,t=1,l[i],r[i],k);x=k;k=0;
insert(0,mo,t=1,r[i]+1,mo,(r[i]-l[i]+1)*x);
}f[num=1]={0,0,0,0,0};
for (i=n;i>=1;i--){
t=0;
find(0,mo,1,l[i],r[i]);t%=mo;
ans=(ans+t*s[i]%mo*h[i]%mo)%mo;k=p[i-1]*q[i+1]%mo;
insert(0,mo,t=1,l[i]+1,r[i],k);x=k;k=0;
insert(0,mo,t=1,r[i]+1,mo,(r[i]-l[i]+1)*x);
}
ans=ans*mi(p[n],mo-2)%mo;
for (i=1;i<=n;i++)
ans=(ans+s[i])%mo;
printf("%lld\n",ans);
}