题目

题目传送门

题目背景

Y901 高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。

题目描述

Y901 高速公路是一条由 $n-1$ 段路以及 $n$ 个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为 $1\sim n$，从收费站 $i$ 行驶到 $i+1$（或从 $i+1$ 行驶到 $i$）需要收取 $v_i$ 的费用。高速路刚建成时所有的路段都是免费的，即所有 $v_i=0$。

政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

无聊的小 A 同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的 $l,r$，在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$，那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?

输入格式

第一行有两个整数，分别表示收费站个数 $n$，和询问与调整费用的总数 $m$。

接下来 $m$ 行，每行表示一次调整或询问，首先有一个字符 $op$。

• 若 $op$ 为 C，则后面有三个整数 $l,r,v$，表示将第 $l$ 个收费站到第 $r$ 个收费站之间所有道路的通行费用增加 $v$。
• 若 $op$ 为 Q，则后面有两个整数 $l,r$，对于给定的 $l,r$，请回答小 A 的问题。

输出格式

对于每次询问，输出一行一个既约分数表示答案。

若答案为一个整数 $a$，请输出 a/1。

样例 #1

样例输入 #1

4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4
1
2
3
4
5
6

样例输出 #1

1/1
8/3
17/6
1
2
3

提示

数据规模与约定

本题共 $10$ 个测试点，各测试点数据规模如下表所示

对于全部的测试点，保证 $1\le n,m\le 10^5$， o p ∈ { C , Q } op \in \{\texttt C, \texttt Q\} op∈{C,Q}，$1\le l\le r\le n$，$-10^4\le v\le 10^4$，在任何时刻，$0\le v_i\le 10^4$。

思路

求期望的题，一般做法有：1.根据期望的线性性期望dp。2.从期望的定义出发。
很显然，这题长得一点也不dp，于是考虑最原始的方法：费用总和/情况数。

考虑对于一段区间 $[l,r]$：
先算分母，即情况数，记区间长度为 $len=r-l+1$，选择 $a$ 收费点时，有 $len$ 个可选择；选择 $b$ 收费点是，还剩 $len-1$ 个可选择，总情况数应为 $len\times (len-1)$。注意到每个 $(a,b)$ 会被算两次，而我们在后面计算分子（费用总和）时，并没有重复统计，所以这里分母为 $\frac{len\times (len-1)}{2}$。

后算分子，即费用总和，这里是个难点。
如果暴力枚举 $a,b$，时间复杂度 $O(le{n}^2)$，不可接受。
考虑贡献法，去算每两个收费站之间的费用被统计了几次。记第 $i$ 个和第 $i+1$ 个收费站之间的费用为 $val[i]$，则对于每一个 $val[i]$，其被统计的次数为第 $l\sim i$ 收费站的个数与第 $i+1\sim r$ 收费站的个数之积，即为 $(i-l+1)\times (r-i)$，所以分子即为 $\sum _{i=l}^{r-1}(i-l+1)\times (r-i)\times val[i]$（注意右端点下标）。

到这里思路都比较自然，可我们现在的时间复杂度是 $O(len)$，还是无法接受，我们需要一个 $log$ 的做法，区间操作，于是想到线段树。
可是，线段树怎么维护这一大坨东西呢？于是我们开始（我最不擅长的，让我暴毙的，使我无从下手的）推式子，把式子中的乘法化开：
$$\sum _{i=l}^{r-1}(i-l+1)\times (r-i)\times val[i]$$
$$=\sum _{i=l}^{r-1}(ir-lr+r-i^2+li-i)\times val[i]$$
$$=(r-lr)\times \sum _{i=l}^{r-1}val[i]+(l+r-1)\times \sum _{i=l}^{r-1}i\times val[i]-\sum _{i=l}^{r-1}{i}^2\times val[i]$$
将和 $i$ 有关的放在 $\sum$ 里后，就可以用线段树维护了，维护 $\sum _{i=l}^{r-1}val[i]$，$\sum _{i=l}^{r-1}i\times val[i]$，$\sum _{i=l}^{r-1}{i}^2\times val[i]$ 三个值即可。

怎么维护呢？查询操作是 trivial 的，需要考虑清楚的是修改操作。
对于 $\sum _{i=l}^{r-1}val[i]$，这就是一个简单的区间加的操作，维护的和每次增加区间长度与 $v$ 的乘积，即线段树中维护的值增加 $r1[k]\times v$，其中 $r1[k]$ 为线段树 $k$ 号节点的区间长度。
对于 $\sum _{i=l}^{r-1}i\times val[i]$，会发现这不是简单的区间加，每个节点的值修改的不一样。记 $r2[k]=\sum _{i=l}^{r}i$（此处的 $l,r$ 为线段树上 $k$ 号节点的左端点右端点），那么线段树中维护的值增加 $r2[k]\times v$。
对于 $\sum _{i=l}^{r-1}{i}^2\times val[i]$，与上面同理，记 $r3[k]=\sum _{i=l}^r{i}^2$，那么线段树中维护的值增加 $r3[k]\times v$。
$r1,r2,r3$ 数组都在 build 操作中预处理即可。

然后就完事了，最后将分子分母约个分即可，时间复杂度 $O(nlogn)$。

---

一些注意点：

• 线段树节点个数为 $n-1$，修改和查询区间为 $[l,r-1]$，但不要手贱先把 $r--$，上述公式里的 $r$ 还是原来的 $r$。
• 懒标记下传时是 $+=$，不是 $=$，否则就变成区间覆盖了。
• r1 数组完全不需要，直接r-l+1即可，只不过代码看上去整齐美观（维护的三个东西代码可以复制粘贴）。。。

确实是不错的一道题，思维链比较长，推式子把我卡住了，线段树运用不够熟练。

反思：遇见带 $\sum$ 的式子，可以将与 $i$ 无关的提出来，与 $i$ 有关的独立开分别计算；线段树维护区间操作，如果每个点修改的大小不同，可以预处理处每个点的贡献。

代码

#include 
#define rep(i, a, b) for (register int i(a); i <= b; ++i)
#define per(i, a, b) for (register int i(a); i >= b; --i)
#define FILE(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define mem(a, x) memset(a, x, sizeof a)
#define pb push_back
#define umap unordered_map
#define pqueue priority_queue
#define mp make_pair
#define PI acos(-1)
#define int long long

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int n, m;

template <typename _T>
void rd(_T &x) {
    int f = 1; x = 0;
    char s = getchar();
    while (s > '9' || s < '0') {if (s == '-') f = -1; s = getchar();}
    while (s >= '0' && s <= '9') x = (x<<3)+(x<<1)+(s^48), s = getchar();
    x *= f;
}

template <typename _T>
void write(_T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x/10);
    putchar(x%10+'0');
    return ;
}

struct seg {
	int tr1[500005], tr2[500005], tr3[500005], r1[500005], r2[500005], r3[500005], tag1[500005], tag2[500005], tag3[500005];
	
	#define ls k<<1
	#define rs k<<1|1
	
	void build(int k, int l, int r) {
		if (l == r) {
			r1[k] = 1;
			r2[k] = l;
			r3[k] = l*l;
			return ;
		}
		int mid = (l+r) >> 1;
		build(ls, l, mid); build(rs, mid+1, r);
		r1[k] = r1[ls]+r1[rs];
		r2[k] = r2[ls]+r2[rs];
		r3[k] = r3[ls]+r3[rs];
		return ;
	}
	
	inline void pushup(int k) {
		int x;
		if (tag1[k]) {
			x = tag1[k];
			tag1[k] = 0;
			tag1[ls] += x;
			tag1[rs] += x;
			tr1[ls] += r1[ls]*x;
			tr1[rs] += r1[rs]*x;
		}
		if (tag2[k]) {
			x = tag2[k];
			tag2[k] = 0;
			tag2[ls] += x;
			tag2[rs] += x;
			tr2[ls] += r2[ls]*x;
			tr2[rs] += r2[rs]*x;
		}
		if (tag3[k]) {
			x = tag3[k];
			tag3[k] = 0;
			tag3[ls] += x;
			tag3[rs] += x;
			tr3[ls] += r3[ls]*x;
			tr3[rs] += r3[rs]*x;
		}
		return ;
	}
	
	void modify(int k, int l, int r, int L, int R, int d) {
		if (l >= L && r <= R) {
			tr1[k] += r1[k]*d;
			tr2[k] += r2[k]*d;
			tr3[k] += r3[k]*d;
			tag1[k] += d;
			tag2[k] += d;
			tag3[k] += d;
//			printf("test %lld %lld %lld %lld %lld\n", l, r, r3[k], d, tr3[k]);
			return ;
		}
		pushup(k);
		int mid = (l+r) >> 1;
		if (L <= mid) modify(ls, l, mid, L, R, d);
		if (R > mid) modify(rs, mid+1, r, L, R, d);
		tr1[k] = tr1[ls]+tr1[rs];
		tr2[k] = tr2[ls]+tr2[rs];
		tr3[k] = tr3[ls]+tr3[rs];
		return ;
	}
	
	int query1(int k, int l, int r, int L, int R) {
		if (l >= L && r <= R) return tr1[k];
		pushup(k);
		int mid = (l+r) >> 1, ret = 0ll;
		if (L <= mid) ret += query1(ls, l, mid, L, R);
		if (R > mid) ret += query1(rs, mid+1, r, L, R);
		return ret;
	}
	
	int query2(int k, int l, int r, int L, int R) {
		if (l >= L && r <= R) return tr2[k];
		pushup(k);
		int mid = (l+r) >> 1, ret = 0ll;
		if (L <= mid) ret += query2(ls, l, mid, L, R);
		if (R > mid) ret += query2(rs, mid+1, r, L, R);
		return ret;
	}
	
	int query3(int k, int l, int r, int L, int R) {
		if (l >= L && r <= R) return tr3[k];
		pushup(k);
		int mid = (l+r) >> 1, ret = 0ll;
		if (L <= mid) ret += query3(ls, l, mid, L, R);
		if (R > mid) ret += query3(rs, mid+1, r, L, R);
		return ret;
	}
} T;

int gcd(int x, int y) {
	if (!y) return x;
	return gcd(y, x%y);
}

signed main() {
	rd(n), rd(m);
	T.build(1, 1, n-1);
	rep(i, 1, m) {
		char opt[5]; scanf("%s", opt);
		if (opt[0] == 'C') {
			int l, r, v;
			rd(l), rd(r), rd(v);
			T.modify(1, 1, n-1, l, r-1, v);
		} else {
			int l, r; rd(l), rd(r);
			int len = r-l+1, fm = len*(len-1)/2;
			int a1 = T.query1(1, 1, n-1, l, r-1), a2 = T.query2(1, 1, n-1, l, r-1), a3 = T.query3(1, 1, n-1, l, r-1);
			int ans = (r-l*r)*a1+(l+r-1)*a2-a3, g = gcd(fm, ans);
			printf("%lld/%lld\n", ans/g, fm/g);
		}
	}
    return 0;
}
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157