【jzoj5232】【NOIP2017模拟A组模拟8.5】【带权排序】【线段树】

题目大意

解题思路

考虑维护f[i]表示填i时当前数期望前面有多少个数比自己小，发现添加一个数对f增加一个等差数列和一段定值，计算贡献时区间求和，可以用线段树维护。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=1e5,ma=1e9,mo=1e9+7;
int n,ans,pon,sum[mn*80+9],tag[mn*80+9],ta2[mn*80+9],son[mn*80+9][2],
s[mn+9],l[mn+9],r[mn+9];
int pow(int x,int y){
int z=1;
while(y){
if(y&1)z=1ll*z*x%mo;
x=1ll*x*x%mo;
y/=2;
 }
 return z;
}
int calc(int x,int y,int z){
 return (1ll*x*z+1ll*(z-1)*z/2%mo*y)%mo;
}
void uptag(int p,int l,int r){
 if((tag[p]||ta2[p])&&(l!=r)){
 int md=(l+r)/2,x=tag[p],y=ta2[p];
if(!son[p][0])son[p][0]=++pon;
if(!son[p][1])son[p][1]=++pon;
int ls=son[p][0],rs=son[p][1];
        tag[ls]=(tag[ls]+x)%mo;
        ta2[ls]=(ta2[ls]+y)%mo;
        sum[ls]=(sum[ls]+calc(x,y,md-l+1))%mo;
        tag[rs]=(tag[rs]+x+1ll*y*(md-l+1))%mo;
        ta2[rs]=(ta2[rs]+y)%mo;
        sum[rs]=(sum[rs]+calc((x+1ll*y*(md-l+1))%mo,y,r-md))%mo;
        tag[p]=ta2[p]=0;
    }
}
void oper(int p,int l,int r,int u,int v,int x,int y){
    uptag(p,l,r);
int md=(l+r)/2;
if((l==u)&&(r==v)){
        sum[p]=(sum[p]+calc(x,y,r-l+1))%mo;
        tag[p]=(tag[p]+x)%mo;
        ta2[p]=(ta2[p]+y)%mo;
return;
    }
if(v<=md){
if(!son[p][0])son[p][0]=++pon;
        oper(son[p][0],l,md,u,v,x,y);
    }else if(md<u){
if(!son[p][1])son[p][1]=++pon;
        oper(son[p][1],md+1,r,u,v,x,y);
    }else{
if(!son[p][0])son[p][0]=++pon;
if(!son[p][1])son[p][1]=++pon;
        oper(son[p][0],l,md,u,md,x,y),
        oper(son[p][1],md+1,r,md+1,v,(x+1ll*y*(md+1-u))%mo,y);
    }
    sum[p]=(sum[son[p][0]]+sum[son[p][1]])%mo;
}
int qury(int p,int l,int r,int u,int v){
    uptag(p,l,r);
int md=(l+r)/2;
if((l==u)&&(r==v))return sum[p];
if(v<=md)return qury(son[p][0],l,md,u,v);
else if(md<u)return qury(son[p][1],md+1,r,u,v);
else return (qury(son[p][0],l,md,u,md)+qury(son[p][1],md+1,r,md+1,v))%mo;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%d",&n);
    fo(i,1,n)scanf("%d%d%d",&s[i],&l[i],&r[i]),ans=(ans+s[i])%mo;
    pon=1;
    fo(i,1,n){
        LL tmp=pow(r[i]-l[i]+1,mo-2),tm2=tmp*s[i]%mo;
        ans=(ans+qury(1,0,ma,l[i],r[i])*tm2)%mo;
        oper(1,0,ma,l[i],r[i],tmp,tmp);
if(r[i]+1<=ma)oper(1,0,ma,r[i]+1,ma,1,0);
    }
    fo(i,0,pon)sum[i]=tag[i]=ta2[i]=son[i][0]=son[i][1]=0;
    pon=1;
    fd(i,n,1){
        LL tmp=pow(r[i]-l[i]+1,mo-2),tm2=tmp*s[i]%mo;
if(r[i]-1>=0)ans=(ans+qury(1,0,ma,max(l[i]-1,0),r[i]-1)*tm2)%mo;
        oper(1,0,ma,l[i],r[i],tmp,tmp);
if(r[i]+1<=ma)oper(1,0,ma,r[i]+1,ma,1,0);
    }
printf("%d",(ans+mo)%mo);
return 0;
}