Steven_MengのBlog

传送门

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

把链上面的操作转化到点上面的的操作,我们像这样编号,点编号为$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$中经常使用的一种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// 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);
}
}
}

 评论