P2221 [HAOI2012]高速公路

传送门

首先，看到区间修改，区间查询就要想到线段树。

把链上面的操作转化到点上面的的操作，我们像这样编号，点编号为 $1...n$ ，边编号为 $1...n-1$

于是修改和查询都对应到了边 $[l,r-1]$

考虑如何算期望值，下面的分母很简单，就是 $C_{r-l+1}^2$ ，从 $r-l+1$ 个点中选出 $2$ 个。

上面的分子是 $\sum _{i=l}^r \sum _{j=l}^r dis(i,j)$ ，比较难算。

不妨从每条边的贡献的角度考虑：

假设现在查询的区间是 $[2,7]$ ，现在算的是编号为 $4$ 的边的贡献，考虑哪些路径会包含这条边。

发现只有左端点是红色箭头，右端点是蓝色箭头的路径会包含这条边。

所以，得出公式 $\sum _{i=l}^r a[i] \times (i-l+1) \times (r-i+1)$

开始大力拆式子，拆成：

$\sum_{i=l}^r a[i] \times (-i^2 + i (l+r) +r-l+1-lr)$

发现这个式子并不复杂，仔细观察，只有 $i$ 是变量，所以很多东西都可以提出来，变成：

$-\sum_{i=l}^r a[i] \times i^2 + (l+r) \sum_{i=l}^r a[i] \times i + (r-l+1-lr) \sum _{i=l}^r a[i]$

所以我们在线段树上面维护以下的东西：

$\sum a[i] \times i^2$

$\sum a[i] \times i$

$\sum a[i]$

而考虑修改，发现 $\sum (a[i]+\Delta) \times i^2 - \sum a[i] \times i^2 = \sum \Delta \times i^2=\Delta \sum i^2$

所以我们通过公式算出 $\sum i^2$ 就可以了。

剩下两种也比较简单。

总结：贡献法是 $\rm OI$ 中经常使用的一种方法

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAXN 100005
#define int long long
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
inline int F1(int x){
    return x*(x+1)/2;
}
inline int F(int l,int r){
    return F1(r)-F1(l-1);
}
inline int G1(int x){
    return x*(x+1ll)/2ll*(2ll*x+1ll)/3ll;
}
inline int G(int l,int r){
    return G1(r)-G1(l-1);
}
int sum1,sum2,sum3;
namespace SegmentTree{
    #define ARG tree[i].l,tree[i].r
    struct node{
        int l,r;
        int val1,val2,val3;
        int tag;
        //val1 a[i]*i^2
        //val2 a[i]*i
        //val3 a[i]
        inline int len(){
            return r-l+1;
        }
    }tree[MAXN<<2];
    #define lc i<<1
    #define rc i<<1|1
    inline void Change(int i,int val){
        tree[i].val1+=val*G(ARG);
        tree[i].val2+=val*F(ARG);
        tree[i].val3+=val*tree[i].len();
        tree[i].tag+=val;
    }
    inline void pushdown(int i){
        if (tree[i].tag){
            Change(lc,tree[i].tag);
            Change(rc,tree[i].tag);
            tree[i].tag=0;
        }
    }
    inline void pushup(int i){
        tree[i].val1=tree[lc].val1+tree[rc].val1;
        tree[i].val2=tree[lc].val2+tree[rc].val2;
        tree[i].val3=tree[lc].val3+tree[rc].val3;
    }
    void Build(int i,int l,int r){
        tree[i].l=l,tree[i].r=r;
        if (l==r) return ;
        int mid=(l+r)>>1;
        Build(lc,l,mid);
        Build(rc,mid+1,r);
    }
    void Update(int i,int L,int R,int val){
        if (L<=tree[i].l&&tree[i].r<=R){
            Change(i,val);
            return ;
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (L<=mid) Update(lc,L,R,val);
        if (mid<R) Update(rc,L,R,val);
        pushup(i);
    }
    void Query(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            sum1+=tree[i].val1,sum2+=tree[i].val2,sum3+=tree[i].val3;
            return ;
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (L<=mid) Query(lc,L,R);
        if (mid<R) Query(rc,L,R);
    }
}
using namespace SegmentTree;
int gcd(int a,int b){
    return a%b==0?b:gcd(b,a%b);
}
#undef int
int main(){
#define int long long
    int n=read(),m=read();
    Build(1,1,n);
    char ch[2];
    while (m--){
        scanf("%s",ch);
        int l=read(),r=read()-1;
        if (ch[0]=='C'){
            int val=read();
            Update(1,l,r,val);
        }
        else{
            sum1=sum2=sum3=0;
            Query(1,l,r);
            int a=-sum1+(l+r)*sum2+(r-l+1-l*r)*sum3;
            int b=F1(r-l+1);
            int g=gcd(a,b);
            printf("%lld/%lld\n",a/g,b/g);
        }
    }
}