题解 P2221 【[HAOI2012]高速公路】

· · 题解

这个题目真的是一个很好的练习自己概率期望的题！

看到什么区间加法，一秒线段树

然后如何维护边之间的和呢？

比如说

1号花费2到2号，2号花费4到3号

把每一条路的花费作为终点处的点的权值就好了

此时每一个点的权值就是

1\rightarrow0,2\rightarrow2,3\rightarrow4

这样就可以了。求 l 到 r 的花费就是 [l+1,r] 的和

用线段树做加法也同理

我们记录一个前缀和数组 sum，然后发现 l 到 r 的花费就是 \text{sum}_r-\text{sum}_l,连-1也没有了超舒服

根据期望的定义(其实就是平均数)

答案就是

\frac {\sum_{i=l}^r\sum_{j=i}^r(sum[j]-sum[i])}{C_{r-l+1}^{2}}

然后呢？下面谁都会求啊，我们考虑上面

用线段树维护这个奇怪的东西

我们根据之前做过的题目，考虑一个套路：

枚举 [l,r] 的每一个位置出现了（被包含了）多少次

比如说区间 [l,r]

所以 $l$ 出现了 $r-l+1$ 次 $l+1$ 被 $[l+1,l+1],...,[l+1,r]$ 包含 也被 $[l,l+1],...,[l,r]$ 包含 共出现 $r-l+r-l=2(r-l)

同理，l+i 被 [l+i,...] 开头的 r-i+1 个区间包含

也被包含l+i-1的r-i+1个区间包含 ([l+i-1,l+i],...,[l+i-1,r])

......

也被包含 l 的 r-i+1 个区间包含 ([l,l+i],...,[l,l+r])

所以我们可以得知第i个数被包含的次数为 (r-i+1)\cdot(i-l+1)

所以上面的答案转化成了

\sum_{i=l}^ra_i\cdot(r-i+1)\cdot(i-l+1)

还是不能维护啊

那就拆开吧！

=\sum_{i=l}^ra_i\cdot(r-i+1)\cdot(i-l+1) =\sum_{i=l}^ra_i\cdot[-i^2+1-lr-l+r+i(l+r)] =\sum_{i=l}^ra_i\cdot[-i^2+(r-l-lr+1)+i(l+r)]

分离 \sum

就

=-\sum_{i=l}^ra_i\cdot i^2+\sum_{i=l}^ra_i(r-l+1-lr)+\sum_{i=l}^ra_ii(l+r) =-\sum_{i=l}^ra_i\cdot i^2+(r-l+1-lr)\sum_{i=l}^ra_i+(l+r)\sum_{i=l}^ra_ii

然后就好像可以用线段树维护了

维护 a_i 的和，设为 sum1

维护 i\cdot a_i 的和，设为 sum2

维护 i^2\cdot a_i 的和，设为 sum3

上面的答案就是-\text{sum}_3+(l+r)\cdot \text{sum}_2+(1-l+r-lr)\cdot \text{sum}_1

但是有区间加法，怎么维护这些的和呢？

设某线段树节点控制的区域为 L,R, 这个区间所有 a 都+=w

有

\text{sum}_1+=(R-L+1)\cdot w \text{sum}_2+=\sum_{i=L}^R[i\cdot (a_i+w)-i\cdot a_i\ ]

即

+=w\sum_{i=L}^Ri

每一个线段树节点额外记录一个\sum_{i=L}^Ri就可以了（这个可以在建树的时候预处理出来，我们设为 sum4)。

\text{sum}_3+=\sum_{i=L}^R[i^2\cdot (a_i+w)-i^2\cdot a_i\ ]

即

+=w\sum_{i=L}^Ri^2

每一个线段树节点再额外记录一个\sum_{i=L}^Ri^2就可以了（这个可以在建树的时候预处理出来，我们设为 sum5）。

于是这题就做完啦！

最后注意要约分啊！

很容易爆 long long 所以建议多开一些 long long。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();};
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-48;ch=getchar();};
    return x*f; 
}
int n,m;
struct node{
    ll sum1,sum2,sum3,sum4,sum5,lazy;//如上文所述
}g[1000001];
inline void pushup(int rt){
    g[rt].sum1=g[rt<<1].sum1+g[rt<<1|1].sum1;
    g[rt].sum2=g[rt<<1].sum2+g[rt<<1|1].sum2;
    g[rt].sum3=g[rt<<1].sum3+g[rt<<1|1].sum3;
}
void build(int rt,int lb,int rb){
    if (lb==rb){g[rt].sum4=1LL*lb;g[rt].sum5=1LL*lb*lb;return;}//预处理sum4，sum5
    int mid=lb+rb>>1;
    build(rt<<1,lb,mid);build(rt<<1|1,mid+1,rb);
    g[rt].sum4=g[rt<<1].sum4+g[rt<<1|1].sum4;
    g[rt].sum5=g[rt<<1].sum5+g[rt<<1|1].sum5;
}
inline void pushdown(int rt,int lb,int rb){
    if (g[rt].lazy){
        int mid=lb+rb>>1,ls=rt<<1,w=g[rt].lazy,rs=rt<<1|1;
        g[ls].lazy+=1LL*w;g[rs].lazy+=1LL*w;
        g[ls].sum1+=1LL*(mid-lb+1)*w;g[rs].sum1+=1LL*(rb-mid)*w;
        g[ls].sum2+=1LL*w*g[ls].sum4;g[rs].sum2+=1LL*w*g[rs].sum4;
        g[ls].sum3+=1LL*w*g[ls].sum5;g[rs].sum3+=1LL*w*g[rs].sum5;
        g[rt].lazy=0;
    }
}
void update(int rt,int lb,int rb,int l,int r,ll w){
    if (lb>r||rb<l) return;
    if (lb>=l&&rb<=r){
        g[rt].sum1+=1LL*(rb-lb+1)*w;g[rt].sum2+=1LL*w*g[rt].sum4;
        g[rt].sum3+=1LL*w*g[rt].sum5;g[rt].lazy+=1LL*w;return;
    }
    pushdown(rt,lb,rb);
    int mid=lb+rb>>1;
    update(rt<<1,lb,mid,l,r,w);update(rt<<1|1,mid+1,rb,l,r,w);
    pushup(rt);
}
void query(int rt,int lb,int rb,int l,int r,ll &sum1,ll &sum2,ll &sum3){//由于想减少代码量以及常数于是就尝试用void记录答案
    if (lb>r||rb<l) return;
    if (lb>=l&&rb<=r){sum1+=g[rt].sum1;sum2+=g[rt].sum2;sum3+=g[rt].sum3;return;}
    pushdown(rt,lb,rb);
    int mid=lb+rb>>1;
    query(rt<<1,lb,mid,l,r,sum1,sum2,sum3);query(rt<<1|1,mid+1,rb,l,r,sum1,sum2,sum3);
}
int main(){
    n=read(),m=read();
    build(1,1,n);
    while (m--){
        char s[12];ll l,r;scanf("%s",s);l=read(),r=read();
        if (s[0]=='C'){
            ll w=read();
            if (l==r) continue;
            update(1,1,n,l+1,r,w);
        }else{
            ll S1=0,S2=0,S3=0;
            query(1,1,n,l+1,r,S1,S2,S3);
            ll Up=-S3+(l+r+1)*S2+(r-(l+1)-(l+1)*r+1)*S1,Down=(r-l+1)*(r-l)/2;//Up是分子，Down是分母
            ll Gcd=__gcd(Up,Down);
            printf("%lld/%lld\n",Up/Gcd,Down/Gcd);//约分
        }
    }
}