这道题还算简单
我们要求的期望值：
$$frac{sum_{i=l}^rsum_{j=l}^rdis[i][j]}{C_{r-l+1}^{2}}$$
当然是上下两部分分别求，下面肥肠容易 ，问题在于如何求上面的
我们珂以把上面的换一个形式（枚举每段路会走几次）：
$$sum_{i=l}^ra[i](r-i+1)(i-l+1)$$
化简一下这个式子：
$$(r-l+1-rl)sum1+(r+l)*sum2-sum3$$
其中(sum1=sum_{i=l}^ra[i])，(sum2=sum_{i=l}^ra[i]*i)，(sum3=sum_{i=l}^ra[i]*i^2)
这样就珂以用线段树维护了
#include <bits/stdc++.h>
#define ll long long
#define N 100005
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline ll read()
{
register ll x=0,f=1;register 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 void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[25];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
struct node{
ll sum[6],tag;
}tr[N<<3];
int n,m;
ll sum1,sum2,sum3;
inline void build(register int x,register int l,register int r)
{
if(l==r)
{
tr[x].sum[4]=1ll*l;
tr[x].sum[5]=1ll*l*l;
return;
}
int mid=l+r>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
tr[x].sum[4]=tr[x<<1].sum[4]+tr[x<<1|1].sum[4];
tr[x].sum[5]=tr[x<<1].sum[5]+tr[x<<1|1].sum[5];
}
inline void work(register int x,register int l,register int r,register ll val)
{
tr[x].sum[1]+=1ll*(r-l+1)*val;
tr[x].sum[2]+=tr[x].sum[4]*val;
tr[x].sum[3]+=tr[x].sum[5]*val;
tr[x].tag+=val;
}
inline void pushdown(register int x,register int l,register int r)
{
int mid=l+r>>1;
work(x<<1,l,mid,tr[x].tag);
work(x<<1|1,mid+1,r,tr[x].tag);
tr[x].tag=0;
}
inline void pushup(register int x)
{
tr[x].sum[1]=tr[x<<1].sum[1]+tr[x<<1|1].sum[1];
tr[x].sum[2]=tr[x<<1].sum[2]+tr[x<<1|1].sum[2];
tr[x].sum[3]=tr[x<<1].sum[3]+tr[x<<1|1].sum[3];
}
inline void change(register int x,register int l,register int r,register int L,register int R,register ll val)
{
if(L<=l&&r<=R)
{
work(x,l,r,val);
return;
}
if(tr[x].tag)
pushdown(x,l,r);
int mid=l+r>>1;
if(L<=mid)
change(x<<1,l,mid,L,R,val);
if(R>mid)
change(x<<1|1,mid+1,r,L,R,val);
pushup(x);
}
inline void query(register int x,register int l,register int r,register int L,register int R)
{
if(L<=l&&r<=R)
{
sum1+=tr[x].sum[1];
sum2+=tr[x].sum[2];
sum3+=tr[x].sum[3];
return;
}
if(tr[x].tag)
pushdown(x,l,r);
int mid=l+r>>1;
if(L<=mid)
query(x<<1,l,mid,L,R);
if(R>mid)
query(x<<1|1,mid+1,r,L,R);
}
inline ll gcd(register ll a,register ll b)
{
return !b?a:gcd(b,a%b);
}
int main()
{
n=read(),m=read();
build(1,1,n);
while(m--)
{
char ch=getchar();
while(ch!='C'&&ch!='Q')
ch=getchar();
ll l=read(),r=read()-1;
if(ch=='C')
{
ll v=read();
change(1,1,n,l,r,v);
}
else
{
sum1=sum2=sum3=0;
query(1,1,n,l,r);
ll ansa=(r-l+1-r*l)*sum1+(r+l)*sum2-sum3;
ll ansb=(r-l+2)*(r-l+1)/2;
ll g=gcd(ansa,ansb);
write(ansa/g),putchar('/'),write(ansb/g),puts("");
}
}
return 0;
}