题目大意：有一条$n$个点，$n-1$条边的链。求一个区间$[L,R]$内随机选出两点$a,b$的期望距离。要求支持修改边权。

看到区间修改和查询，想到线段树。

考虑一个区间内总距离和：

因为一条边会被一个在它左侧的点和一个在它右侧的点覆盖，所以总距离和可以表示为：

$\sum_{i=l}^{r} a_i*(r-i+1)*(i-l+1)$

如果将式子展开，得到$ \sum {i=l}{r} a_i*(rl+ri+r+il-i*i+1-l)$

将后面的式子按i的次数分类

$\sum_{i=l}^{r} a[i]*(rl+1+r-l)+a[i]*(r+l)*i+a[i]*i*i$

发现后两项在更新时不好计算，所以再额外记录$sum4$记录$\sum i$，$sum5$记录$\sum i*i$，这样在更新的时候可以方便的用这两个常量计算答案。

 

#include
     
      #include
      
       #include
       
        #include
        
         #define mid (l+r)/2#define N 100005#define log 40#define lowbit(x) x&-x#define mod 998244353#define int long longusing namespace std;int sum1[400005],sum2[400005],sum3[400005],sum4[400005],sum5[400005],lazy[400005];int a[400005];int ans1,ans2,ans3;int n,m;int ls(int x){return x<<1;}int rs(int x){return x<<1|1;}void calc1(int now){	sum4[now]=sum4[ls(now)]+sum4[rs(now)];	sum5[now]=sum5[ls(now)]+sum5[rs(now)];}void calc2(int now){	sum1[now]=sum1[ls(now)]+sum1[rs(now)];	sum2[now]=sum2[ls(now)]+sum2[rs(now)];	sum3[now]=sum3[ls(now)]+sum3[rs(now)];}void build(int now,int l,int r){	if(l==r)	{		sum4[now]=l;		sum5[now]=l*l;		return;	}	build(ls(now),l,mid);	build(rs(now),mid+1,r);	calc1(now);}void work(int now,int l,int r,int k){	sum1[now]+=k*(r-l+1);	sum2[now]+=k*sum4[now];	sum3[now]+=k*sum5[now];	lazy[now]+=k;}void update(int now,int l,int r,int ll,int rr,int k){	if(ll<=l&&r<=rr)	{		work(now,l,r,k);		return;	}	if(lazy[now])	{		work(ls(now),l,mid,lazy[now]);		work(rs(now),mid+1,r,lazy[now]);		lazy[now]=0;	}	if(mid>=ll)	    update(ls(now),l,mid,ll,rr,k);	if(mid
         
          =ll)		query(ls(now),l,mid,ll,rr);	if(mid
          
           '9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}int gcd(int a,int b){return(!b)?a:gcd(b,a%b);}signed main(){ scanf("%lld%lld",&n,&m); build(1,1,n); for(int i=1;i<=m;i++) { char ch; cin>>ch; if(ch=='C') { int l,r,v; scanf("%lld%lld%lld",&l,&r,&v); r--; update(1,1,n,l,r,v); } else { int l,r; scanf("%lld%lld",&l,&r); r--; ans1=ans2=ans3=0; query(1,1,n,l,r); int ans=(r-l+1-r*l)*ans1+(r+l)*ans2-ans3; int q=gcd(ans,(r-l+2)*(r-l+1)/2); printf("%lld/%lld\n",ans/q,(r-l+2)*(r-l+1)/2/q); } } return 0;}