JZOJ 5232【NOIP2017模拟】带权排序(概率,线段树)

时间:2022-12-17 20:19:48

Description

JZOJ 5232【NOIP2017模拟】带权排序(概率,线段树)

Solution

我们知道要求的是 siE(pi) ,那么我们的目的就是对于每个数求出它的期望排名。一个数排名的期望就是对于前面的数小于等于它的期望和后面的数小于它的期望(题目还有一个要求ai=aj时pi

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);
}