「2020冬令营提高组」rng

题目链接

题意

长度为 $n$ 的序列 $a$ 满足 $a_i$ 为 $[l_i,r_i]$ 中随机一实数，求该序列逆序对个数的期望值。

思路

发现每个 $a_i$ 对答案的贡献即为 $\sum_{j=i+1}^na_i>a_j$。

从后往前考虑：

由于在实数范围内，整数边界不予考虑。

记 $c_i$ 为 $(i-1,i]$ 中目前出现实数的期望个数，$s_{i,j}$ 为 $\sum_{k=i}^jc_k$，$s^\prime_{i,j}$ 为 $\sum_{k=i}^jk\cdot c_k$。

查询

假设 $l_i=2,r_i=5$，$res_{2,5}$ 即为 $c_0+c_1+c_2+\frac{\frac52c_3+\frac32c_4+\frac12c_5}3$。

如何优化？

$\begin{aligned} res_{2,5}&=s_{0,2}+\frac{\frac{11}2(c_3+c_4+c_5)-(3c_3+4c_4+5c_5)}{5-2}\\ &=s_{0,2}+\frac{(5+\frac12)s_{3,5}-s^\prime_{3,5}}{5-2} \end{aligned}$

由此推出查询公式：

$\begin{aligned} res_{l,r}&=s_{0,l}+\frac{(r+\frac12)s_{l+1,r}-s^\prime_{l+1,r}}{r-l}\\ &=\frac{r*s_{0,l}-l*s_{0,l}+r*s_{l+1,r}+\frac12s_{l+1,r}-s^\prime_{l+1,r}}{r-l}\\ &=\frac{(r+\frac12)s_{0,r}-(l+\frac12)s_{0,l}+s^\prime_{0,l}-s^\prime_{0,r}}{r-l} \end{aligned}$

修改

每次计算完 $a_i$ 对答案的贡献，就要用 $a_i$ 更新 $s$ 和 $s^\prime$ 数组。

区间 $[l_i,r_i]$ 对 $c$ 数组的贡献为：

对于每个 $l_i<j\leq r_i$，$c_j\gets c_j+\frac1{r_i-l_i}$ 即可。

实现

不难看出，$s,s^\prime$ 数组需要维护区间和与区间修改，用线段树维护。

$l_i,r_i$ 较大，需要离散化。

在离散化+线段树中，维护 $[l,r]$ 的线段树实际维护范围为 $(p_{l-1},p_r]$（其中 $p$ 为映射）。

代码

#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
const int mod=998244353;
const long long inv2=(mod+1)>>1;
int n,siz,p[300001];
map<int,int>m;
long long ans;
struct number {
    int l,r,ll;
    int ml,mr,mll;
}a[100001];
struct seg_tree {
    int l,r;
    long long val,tag;
}t1[1200001],t2[1200001];
void make_map()
{
    for(int i=1,j=0;i<=n;++i) {
        p[++j]=a[i].l,p[++j]=a[i].r,p[++j]=a[i].ll;
    }
    sort(p+1,p+siz+1);
    for(int i=1,j=0;i<=siz;++i) {
        if(p[i]!=p[i-1])
        {
            m[p[i]]=++j;
            p[j]=p[i];
        }
    }
    for(int i=1;i<=n;++i) {
        a[i].ml=m[a[i].l],a[i].mr=m[a[i].r],a[i].mll=m[a[i].ll];
    }
    return;
}
void build1(int num,int l,int r)
{
    t1[num]=seg_tree{l,r,0,0};
    if(l==r) {
        return;
    }
    int mid=(l+r)>>1;
    build1(num<<1,l,mid),build1(num<<1|1,mid+1,r);
    return;
}
void build2(int num,int l,int r)
{
    t2[num]=seg_tree{l,r,0,0};
    if(l==r) {
        return;
    }
    int mid=(l+r)>>1;
    build2(num<<1,l,mid),build2(num<<1|1,mid+1,r);
    return;
}
void push_down1(int num)
{
    if(!t1[num].tag) {
        return;
    }
    t1[num<<1].val=(t1[num<<1].val+t1[num].tag*(p[t1[num<<1].r]-p[t1[num<<1].l-1])%mod)%mod;
    t1[num<<1].tag=(t1[num<<1].tag+t1[num].tag)%mod;
    t1[num<<1|1].val=(t1[num<<1|1].val+t1[num].tag*(p[t1[num<<1|1].r]-p[t1[num<<1|1].l-1])%mod)%mod;
    t1[num<<1|1].tag=(t1[num<<1|1].tag+t1[num].tag)%mod;
    t1[num].tag=0;
    return;
}
void push_down2(int num)
{
    if(!t2[num].tag) {
        return;
    }
    t2[num<<1].val=(t2[num<<1].val+t2[num].tag*(p[t2[num<<1].l-1]+1+p[t2[num<<1].r])%mod*(p[t2[num<<1].r]-p[t2[num<<1].l-1])%mod*inv2%mod)%mod;
    t2[num<<1].tag=(t2[num<<1].tag+t2[num].tag)%mod;
    t2[num<<1|1].val=(t2[num<<1|1].val+t2[num].tag*(p[t2[num<<1|1].l-1]+1+p[t2[num<<1|1].r])%mod*(p[t2[num<<1|1].r]-p[t2[num<<1|1].l-1])%mod*inv2%mod)%mod;
    t2[num<<1|1].tag=(t2[num<<1|1].tag+t2[num].tag)%mod;
    t2[num].tag=0;
    return;
}
void change1(int num,int l,int r,long long val)
{
    if((t1[num].l>r)||(t1[num].r<l)) {
        return;
    }
    if((t1[num].l>=l)&&(t1[num].r<=r)) {
        t1[num].val=(t1[num].val+val*(p[t1[num].r]-p[t1[num].l-1]))%mod;
        t1[num].tag=(t1[num].tag+val)%mod;
        return;
    }
    push_down1(num);
    change1(num<<1,l,r,val),change1(num<<1|1,l,r,val);
    t1[num].val=(t1[num<<1].val+t1[num<<1|1].val)%mod;
    return;
}
void change2(int num,int l,int r,long long val)
{
    if((t2[num].l>r)||(t2[num].r<l)) {
        return;
    }
    if((t2[num].l>=l)&&(t2[num].r<=r)) {
        t2[num].val=(t2[num].val+val*(p[t2[num].l-1]+1+p[t2[num].r])%mod*(p[t2[num].r]-p[t2[num].l-1])%mod*inv2%mod)%mod;
        t2[num].tag=(t2[num].tag+val)%mod;
        return;
    }
    push_down2(num);
    change2(num<<1,l,r,val),change2(num<<1|1,l,r,val);
    t2[num].val=(t2[num<<1].val+t2[num<<1|1].val)%mod;
    return;
}
long long query1(int num,int l,int r)
{
    if((t1[num].l>r)||(t1[num].r<l)) {
        return 0;
    }
    if((t1[num].l>=l)&&(t1[num].r<=r)) {
        return t1[num].val;
    }
    push_down1(num);
    return (query1(num<<1,l,r)+query1(num<<1|1,l,r))%mod;
}
long long query2(int num,int l,int r)
{
    if((t2[num].l>r)||(t2[num].r<l)) {
        return 0;
    }
    if((t2[num].l>=l)&&(t2[num].r<=r)) {
        return t2[num].val;
    }
    push_down2(num);
    return (query2(num<<1,l,r)+query2(num<<1|1,l,r))%mod;
}
long long pow(long long num,long long times)
{
    long long res=1;
    while(times) {
        if(times&1) {
            res=res*num%mod;
        }
        num=num*num%mod,times>>=1;
    }
    return res;
}
int main()
{
    freopen("rng.in","r",stdin);
    freopen("rng.out","w",stdout);
    scanf("%d",&n);
    siz=n*3;
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].ll=a[i].l+1;
    }
    make_map();
    build1(1,1,siz),build2(1,1,siz);
    for(int i=n;i;--i) {
        ans=(ans+((a[i].r+inv2)*query1(1,0,a[i].mr)%mod-(a[i].l+inv2)*query1(1,0,a[i].ml)%mod+query2(1,0,a[i].ml)-query2(1,0,a[i].mr))%mod*pow(a[i].r-a[i].l,mod-2)%mod)%mod;
        change1(1,a[i].mll,a[i].mr,pow(a[i].r-a[i].l,mod-2));
        change2(1,a[i].mll,a[i].mr,pow(a[i].r-a[i].l,mod-2));
    }
    printf("%lld\n",(ans+mod)%mod);
    return 0;
}