[HAOI2012] 高速公路

题意

Y901 高速公路是一条由 段路以及 个收费站组成的东西向的链，收费站依次编号为 ，从收费站 行驶到 (或从 行驶到 ) 需要收取一定的费用，高速路刚建成时所有的路段都是免费的。

要求动态维护 个操作：

1. 将收费站 之间的路上的收费加 （可能是负数）.
2. 求对于给定的 ，在第 到 个收费站里等概率随机取出两个不同的收费站 和 ，那么从 行驶到 期望花费的费用.

.

分析

这里的期望即平均值，那么

考虑维护分子，把它改写为用边的贡献次数求和

假设第 个收费站后面的路的收费是 ，那么从 到 的收费站的费用之和

考虑用线段树维护 ，考虑区间加的时候

维护

直接维护呢

维护

.

根据

那么

维护

区间加：.

根据

那么

最后再 GCD 一下就行

代码

#include<cstdio>
#define int long long
using namespace std;
const int N=1e5+5,SGT=1<<18;
int n,m;

struct segment{int l,r;};
segment t[SGT];
int s1[SGT],s2[SGT],s3[SGT],tg[SGT];

int S2(int l,int r){return r*(r+1)/2-l*(l-1)/2;}
int S3(int l,int r){return r*(r+1)*(2*r+1)/6-l*(l-1)*(2*l-1)/6;}

void pushup(int rt){
    s1[rt]=s1[rt<<1]+s1[rt<<1|1];
    s2[rt]=s2[rt<<1]+s2[rt<<1|1];
    s3[rt]=s3[rt<<1]+s3[rt<<1|1];
}
void modify(int rt,int v){
    s1[rt]+=(t[rt].r-t[rt].l+1)*v;
    s2[rt]+=S2(t[rt].l,t[rt].r)*v;
    s3[rt]+=S3(t[rt].l,t[rt].r)*v;
    tg[rt]+=v;
}
void pushdown(int rt){
    modify(rt<<1,tg[rt]);
    modify(rt<<1|1,tg[rt]);
    tg[rt]=0;
}
void build(int l,int r,int rt){
    t[rt].l=l,t[rt].r=r;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(l,mid,rt<<1),build(mid+1,r,rt<<1|1);
}
void add(int L,int R,int v,int rt){
    if(L<=t[rt].l&&t[rt].r<=R){modify(rt,v);return;}
    if(tg[rt])pushdown(rt);
    if(L<=t[rt<<1].r)add(L,R,v,rt<<1);
    if(t[rt<<1].r<R)add(L,R,v,rt<<1|1);
    pushup(rt);
}
int sum1,sum2,sum3;
void query(int L,int R,int rt){
    if(L<=t[rt].l&&t[rt].r<=R){sum1+=s1[rt],sum2+=s2[rt],sum3+=s3[rt];
        return ;
    }
    if(tg[rt])pushdown(rt);
    if(L<=t[rt<<1].r)query(L,R,rt<<1);
    if(t[rt<<1].r<R)query(L,R,rt<<1|1);
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
signed main(){
    scanf("%lld%lld",&n,&m);
    build(1,n,1);
    for(int i=1,l,r,v;i<=m;i++){char opt[5];
        scanf("%s%lld%lld",opt,&l,&r),--r;// 点化线段！
        if(opt[0]=='C')scanf("%lld",&v),add(l,r,v,1);
        else {
            sum1=sum2=sum3=0;
            query(l,r,1);
            int a=-sum3+(l+r)*sum2-(r+1)*(l-1)*sum1,b=(r-l+2)*(r-l+1)/2,g=gcd(a,b);
            printf("%lld/%lld\n",a/g,b/g);
        }
    }
    return 0;
}