【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=e5,ma=e9,mo=e9+;
int n,ans,pon,sum[mn*80+],tag[mn*80+],ta2[mn*80+],son[mn*80+][],
    s[mn+],l[mn+],r[mn+];
int pow(int x,int y){
    int z=;
    while(y){
        if(y&)z=ll*z*x%mo;
        x=ll*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)/,x=tag[p],y=ta2[p];
        if(!son[p][])son[p][]=++pon;
        if(!son[p][])son[p][]=++pon;
        int ls=son[p][],rs=son[p][];
        tag[ls]=(tag[ls]+x)%mo;
        ta2[ls]=(ta2[ls]+y)%mo;
        sum[ls]=(sum[ls]+calc(x,y,md-l+))%mo;
        tag[rs]=(tag[rs]+x+ll*y*(md-l+))%mo;
        ta2[rs]=(ta2[rs]+y)%mo;
        sum[rs]=(sum[rs]+calc((x+ll*y*(md-l+))%mo,y,r-md))%mo;
        tag[p]=ta2[p]=;
    }
}
void oper(int p,int l,int r,int u,int v,int x,int y){
    uptag(p,l,r);
    int md=(l+r)/;
    if((l==u)&&(r==v)){
        sum[p]=(sum[p]+calc(x,y,r-l+))%mo;
        tag[p]=(tag[p]+x)%mo;
        ta2[p]=(ta2[p]+y)%mo;
        return;
    }
    if(v<=md){
        if(!son[p][])son[p][]=++pon;
        oper(son[p][],l,md,u,v,x,y);
    }else if(md<u){
        if(!son[p][])son[p][]=++pon;
        oper(son[p][],md+,r,u,v,x,y);
    }else{
        if(!son[p][])son[p][]=++pon;
        if(!son[p][])son[p][]=++pon;
        oper(son[p][],l,md,u,md,x,y),
        oper(son[p][],md+,r,md+,v,(x+ll*y*(md+-u))%mo,y);
    }
    sum[p]=(sum[son[p][]]+sum[son[p][]])%mo;
}
int qury(int p,int l,int r,int u,int v){
    uptag(p,l,r);
    int md=(l+r)/;
    if((l==u)&&(r==v))return sum[p];
    if(v<=md)return qury(son[p][],l,md,u,v);
    else if(md<u)return qury(son[p][],md+,r,u,v);
    else return (qury(son[p][],l,md,u,md)+qury(son[p][],md+,r,md+,v))%mo;
}
int main(){
    freopen("sort.in","r",stdin);
    freopen("sort.out","w",stdout);
    scanf("%d",&n);
    fo(i,,n)scanf("%d%d%d",&s[i],&l[i],&r[i]),ans=(ans+s[i])%mo;
    pon=;
    fo(i,,n){
        LL tmp=pow(r[i]-l[i]+,mo-),tm2=tmp*s[i]%mo;
        ans=(ans+qury(,,ma,l[i],r[i])*tm2)%mo;
        oper(,,ma,l[i],r[i],tmp,tmp);
        if(r[i]+<=ma)oper(,,ma,r[i]+,ma,,);
    }
    fo(i,,pon)sum[i]=tag[i]=ta2[i]=son[i][]=son[i][]=;
    pon=;
    fd(i,n,){
        LL tmp=pow(r[i]-l[i]+,mo-),tm2=tmp*s[i]%mo;
        if(r[i]->=)ans=(ans+qury(,,ma,max(l[i]-,),r[i]-)*tm2)%mo;
        oper(,,ma,l[i],r[i],tmp,tmp);
        if(r[i]+<=ma)oper(,,ma,r[i]+,ma,,);
    }
    printf("%d",(ans+mo)%mo);
    return ;
}