这道题有一种解法是维护区间和，区间和
×
i
\times i
×i，区间和
×
i
2
\times i^2
×i2，但是这就需要很多的数学推导，这里有一种不同的方法，几乎不需要任何数学推导
你只需要会
因为这道题的信息在边上，所以我们可以考虑让线段树存 ( l , r ) (l,r) (l,r)之间的边的信息
首先确定我们需要维护什么内容，因为这道题是选择点是等概率的，所以我们可以先求出所有方案的综合，再除以
C
s
i
z
2
C_{siz}^2
Csiz2就可以了
所以显然我们需要维护一个所有方案的费用总和
a
n
s
ans
ans
但是只维护这一个显然是不行的，考虑我们合并两棵子树的信息的时候
我们的答案应该包括两个端点都在左边的情况，也就是
a
n
s
[
l
s
o
n
]
ans[lson]
ans[lson]和
a
n
s
[
r
s
o
n
]
ans[rson]
ans[rson]
但是这是不够的，因为两个端点有可能在
m
i
d
mid
mid的两边，也就是一个在左儿子的区间，一个在右儿子的区间
那么这种情况的答案是什么呢？
我们考虑让每个点走到
m
i
d
mid
mid，也就是对于一条边
(
x
,
y
)
(x,y)
(x,y)，我们把它拆成
(
x
,
m
i
d
)
(x,mid)
(x,mid)和
(
m
i
d
,
y
)
(mid,y)
(mid,y)两段
对于左半部分的每一个点，他都需要和右半部分的每一个点连一条边，也就是说每个点都要向 m i d mid mid走 s i z [ r s o n ] − 1 siz[rson]-1 siz[rson]−1次，同理，右半部分的每个点都要向左半部分的每个点连一条边，也就是说右半部分每个点都要向 m i d mid mid走 s i z [ l s o n ] − 1 siz[lson]-1 siz[lson]−1次，然后考虑快速的维护这一信息，我们需要再维护两（三）个量
那么这个时候我们的 a n s ans ans就可以快速更新了，在合并两棵子树的时候：
a
n
s
[
i
]
=
a
n
s
[
l
s
o
n
]
+
a
n
s
[
r
s
o
n
]
+
t
o
r
[
l
s
o
n
]
×
(
s
i
z
[
r
s
o
n
]
−
1
)
+
t
o
l
[
r
s
o
n
]
×
(
s
i
z
[
l
s
o
n
]
−
1
)
ans[i]=ans[lson]+ans[rson]+tor[lson]\times (siz[rson]-1)+tol[rson]\times (siz[lson]-1)
ans[i]=ans[lson]+ans[rson]+tor[lson]×(siz[rson]−1)+tol[rson]×(siz[lson]−1)
注意这里
−
1
-1
−1的原因是我们不需要走到
m
i
d
mid
mid，但是因为我们线段树存的是区间，所以
m
i
d
mid
mid这里左右子树是有交集的
那么现在又来了个问题，我们怎么更新
t
o
l
tol
tol和
t
o
r
tor
tor呢？
其实很简单，
t
o
l
[
i
]
tol[i]
tol[i]显然应该包含
t
o
l
[
l
s
o
n
]
tol[lson]
tol[lson]，同时我们又需要让右子树中的每一个节点都再走一个左子树的费用，所以我们还需要维护一个
那么
t
o
l
[
i
]
=
t
o
l
[
l
s
o
n
]
+
t
o
l
[
r
s
o
n
]
+
s
u
m
[
l
s
o
n
]
×
(
s
i
z
[
r
s
o
n
]
−
1
)
tol[i]=tol[lson]+tol[rson]+sum[lson]\times (siz[rson]-1)
tol[i]=tol[lson]+tol[rson]+sum[lson]×(siz[rson]−1)
t
o
r
tor
tor的维护方法和
t
o
l
tol
tol差不多，
s
u
m
sum
sum维护也挺简单，不说了
那么这样的话我们把合并子树的问题解决掉了，接下来还有一个问题就是对于区间修改怎么做
还是一个一个来说吧，首先是
a
n
s
ans
ans
显然，
a
n
s
ans
ans应该加上的值是
v
×
v\times
v×区间中所有边的长度和
比如对于这一个区间，我们分别考虑长度不同的边分别有几条
手画过丑勿喷
我们会发现对于一个长度为
s
i
z
siz
siz的区间，他拥有一条长度为
s
i
z
−
1
siz-1
siz−1的边，两条
s
i
z
−
2
siz-2
siz−2的边…
s
i
z
siz
siz条
s
i
z
−
s
i
z
=
0
siz-siz=0
siz−siz=0的边，转化成数学式子就是
∑
i
=
1
s
i
z
i
×
(
s
i
z
−
i
)
\sum_{i=1}^{siz} i\times(siz-i)
∑i=1sizi×(siz−i)，然后我们拆开这个式子，得到
∑
i
=
1
s
i
z
(
i
×
s
i
z
+
i
2
)
\sum_{i=1}^{siz} (i\times siz+i^2)
∑i=1siz(i×siz+i2)，也就是
s
i
z
×
∑
i
=
1
s
i
z
i
+
∑
i
=
1
s
i
z
s
i
z
2
siz\times \sum_{i=1}^{siz} i+\sum_{i=1}^{siz}siz^2
siz×∑i=1sizi+∑i=1sizsiz2，然后根据等差数列求和公式和前
n
n
n项平方和公式，我们可以得到对于一个长度为
s
i
z
siz
siz的区间，当每条边的费用增加
v
v
v之后，答案应该增加
v
×
(
s
i
z
×
s
i
z
(
s
i
z
−
1
)
2
−
s
i
z
(
s
i
z
+
1
)
(
2
×
s
i
z
+
1
)
6
)
v\times(siz\times \frac{siz(siz-1)}{2}-\frac{siz(siz+1)(2\times siz+1)}{6})
v×(siz×2siz(siz−1)−6siz(siz+1)(2×siz+1))
其实可以进一步分解，但是懒
接下来是
t
o
l
tol
tol和
t
o
r
tor
tor
这个其实很简单，加上
v
×
∑
i
=
1
s
i
z
−
1
i
v\times \sum_{i=1}^{siz-1} i
v×∑i=1siz−1i就可以
注意这里为什么只加到
s
i
z
−
1
siz-1
siz−1呢？因为左端点是不用走到左端点的
t
o
r
tor
tor同理
s
u
m
sum
sum不讲
然后就没了，写得时候注意一下细节就可以了
感觉这种方法比维护
i
2
i^2
i2什么的方法要好想一点，代码实现也不难，而且不用去找
h
a
c
k
hack
hack数据，毕竟这个样例强度海星
下面是代码啦：
#include <bits/stdc++.h>
using namespace std;
# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)
typedef long long ll;
const int N=1e5+5;
template<typename T> void read(T &x){
x=0;int f=1;
char c=getchar();
for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
x*=f;
}
int n,m;
struct node{
int l,r;
ll ans,tol,tor,siz,sum;
ll tag;
}seg[N<<2];
# define lc (u<<1)
# define rc (u<<1|1)
ll gcd(ll a,ll b){
if(!b)return a;
return gcd(b,a%b);
}
node merge(node l,node r){
node res;
res.l=l.l,res.r=r.r;
res.ans=l.ans+r.ans+l.tor*(r.siz-1)+r.tol*(l.siz-1);
res.tol=l.tol+r.tol+l.sum*(r.siz-1);
res.tor=l.tor+r.tor+r.sum*(l.siz-1);
res.siz=res.r-res.l+1;
res.sum=l.sum+r.sum;
res.tag=0;
return res;
}
void renew(int u,ll k){
ll siz=seg[u].siz;
seg[u].ans+=k*(siz*siz*(siz+1)/2-siz*(siz+1)*(2*siz+1)/6);
seg[u].tol+=k*(siz*(siz-1)/2);
seg[u].tor+=k*(siz*(siz-1)/2);
seg[u].sum+=k*(siz-1);
}
void pushdown(int u){
renew(lc,seg[u].tag);
renew(rc,seg[u].tag);
seg[lc].tag+=seg[u].tag;
seg[rc].tag+=seg[u].tag;
seg[u].tag=0;
}
void build(int u,int l,int r){
seg[u].l=l,seg[u].r=r;
seg[u].siz=r-l+1;
if(r==l+1)return;
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid,r);
}
void update(int u,int l,int r,ll k){
if(seg[u].l>=l&&seg[u].r<=r){
renew(u,k);
seg[u].tag+=k;
return;
}
if(seg[u].tag)pushdown(u);
int mid=seg[u].l+seg[u].r>>1;
if(l<mid)update(lc,l,r,k);
if(r>mid)update(rc,l,r,k);
seg[u]=merge(seg[lc],seg[rc]);
}
node query(int u,int l,int r){
if(seg[u].l>=l&&seg[u].r<=r)return seg[u];
if(seg[u].tag)pushdown(u);
int mid=seg[u].l+seg[u].r>>1;
if(r<=mid)return query(lc,l,r);
if(l>=mid)return query(rc,l,r);
return merge(query(lc,l,r),query(rc,l,r));
}
int main()
{
read(n),read(m);
build(1,1,n);
Rep(i,1,m){
char opt[10];
ll x,y,k;
scanf("%s",opt);
read(x),read(y);
if(opt[0]=='C')read(k),update(1,x,y,k);
else{
ll fz=query(1,x,y).ans;
ll fm=1ll*(y-x+1)*(y-x)/2;
ll _g=gcd(fm,fz);
printf("%lld/%lld\n",fz/_g,fm/_g);
}
}
return 0;
}