Description
Solution
我们知道要求的是
Code
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int maxn=1e5+7,mo=1e9+7;
typedef long long ll;
struct node{
ll l,r;
ll sum,s,k,bz;
}t[maxn*100];
ll i,j,k,l,n,m,root,num,da;
ll ans,ni[maxn],ni2;
struct nod{
ll a,l,r;
}a[maxn];
ll qsm(ll x,ll y){
ll z=1;
for(;y;y/=2,x=x*x%mo)if(y&1)z=z*x%mo;
return z;
}
void down(ll x,ll l,ll r){
ll y=t[x].l,z=t[x].r;
if(t[x].s||t[x].k){
if(!y)t[y=t[x].l=++num]=(node){0,0,0,0,0,0};
if(!z)t[z=t[x].r=++num]=(node){0,0,0,0,0,0};
ll mid=(l+r)/2,s=t[x].s,k=t[x].k,ss=(s+(mid-l)*t[x].k%mo)%mo;
(t[y].sum+=(s+ss)%mo*(mid-l+1)%mo*ni2%mo)%=mo;(t[y].s+=s)%=mo,(t[y].k+=k)%=mo;
s=(ss+k)%mo;ss=(t[x].s+(r-l)*k%mo)%mo;
(t[z].sum+=(s+ss)%mo*(r-mid)%mo*ni2%mo)%=mo;(t[z].s+=s)%=mo,(t[z].k+=k)%=mo;
t[x].s=t[x].k=0;
}
if(t[x].bz){
if(!y)t[y=t[x].l=++num]=(node){0,0,0,0,0,0};
if(!z)t[z=t[x].r=++num]=(node){0,0,0,0,0,0};
ll mid=(l+r)/2;
(t[y].sum+=(mid-l+1)*t[x].bz%mo)%=mo;(t[z].sum+=(r-mid)*t[x].bz%mo)%=mo;
(t[y].bz+=t[x].bz)%=mo;(t[z].bz+=t[x].bz)%=mo;
t[x].bz=0;
}
}
void change1(ll &x,ll l,ll r,ll y,ll z,ll s,ll k){
if(y>z)return;
if(!x)t[x=++num]=(node){0,0,0,0,0,0};
if(l==y&&r==z){
(t[x].sum+=(s*2%mo+(r-l)*k%mo)%mo*(r-l+1)%mo*ni2%mo)%=mo;
(t[x].s+=s)%=mo,(t[x].k+=k)%=mo;
return;
}
down(x,l,r);
ll mid=(l+r)/2;
if(z<=mid)change1(t[x].l,l,mid,y,z,s,k);
else if(y>mid)change1(t[x].r,mid+1,r,y,z,s,k);
else{
change1(t[x].l,l,mid,y,mid,s,k);
change1(t[x].r,mid+1,r,mid+1,z,(s+(mid-y+1)*k%mo)%mo,k);
}
t[x].sum=0;if(t[x].l)t[x].sum=t[t[x].l].sum;
if(t[x].r)(t[x].sum+=t[t[x].r].sum)%=mo;
}
void change2(ll &x,ll l,ll r,ll y,ll z,ll o){
if(y>z)return;
if(!x)t[x=++num]=(node){0,0,0,0,0,0};
if(l==y&&r==z){
(t[x].sum+=(r-l+1)*o%mo)%=mo;
(t[x].bz+=o)%=mo;
return;
}
down(x,l,r);
ll mid=(l+r)/2;
if(z<=mid)change2(t[x].l,l,mid,y,z,o);
else if(y>mid)change2(t[x].r,mid+1,r,y,z,o);
else{
change2(t[x].l,l,mid,y,mid,o);
change2(t[x].r,mid+1,r,mid+1,z,o);
}
t[x].sum=0;if(t[x].l)t[x].sum=t[t[x].l].sum;
if(t[x].r)(t[x].sum+=t[t[x].r].sum)%=mo;
}
ll find(ll x,ll l,ll r,ll y,ll z){
if(!x)return 0;
if(l==y&&r==z)return t[x].sum;
down(x,l,r);
ll mid=(l+r)/2;
if(z<=mid)return find(t[x].l,l,mid,y,z);
else if(y>mid)return find(t[x].r,mid+1,r,y,z);
else return(find(t[x].l,l,mid,y,mid)+find(t[x].r,mid+1,r,mid+1,z))%mo;
}
int main(){
freopen("sort.in","r",stdin);
freopen("sort.out","w",stdout);
scanf("%d",&n);ni2=(mo+1)/2;
fo(i,1,n)scanf("%d%d%d",&a[i].a,&a[i].l,&a[i].r),da=max(da,a[i].r),ans=(ans+a[i].a)%mo,ni[i]=qsm(a[i].r-a[i].l+1,mo-2);
fo(i,1,n){
(ans+=a[i].a*find(root,0,da,a[i].l,a[i].r)%mo*ni[i]%mo)%=mo;
change1(root,0,da,a[i].l,a[i].r,ni[i],ni[i]);
change2(root,0,da,a[i].r+1,da,1);
}
root=num=0;t[1]=(node){0,0,0,0,0,0};
fod(i,n,1){
(ans+=a[i].a*find(root,0,da,a[i].l,a[i].r)%mo*ni[i]%mo)%=mo;
change1(root,0,da,a[i].l+1,a[i].r,ni[i],ni[i]);
change2(root,0,da,a[i].r+1,da,1);
}
printf("%lld\n",ans);
}