题目描述
Y901 高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。
Y901 高速公路是一条由 $n-1$ 段路以及 $n$ 个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为$1 – n$ ，从收费站i行驶到 $i+1$ (或从 $i+1$ 行驶到 $i$ )需要收取 $V_i$ 的费用。高速路刚建成时所有的路段都是免费的。
政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。
无聊的小A同学总喜欢研究一些稀奇古怪的问题，他开车在这条高速路上行驶时想到了这样一个问题:对于给定的 $l, r $ $(l<r)$ ,在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$ ，那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?
输入格式
第一行 $2$ 个正整数 $n, m$，表示有 $n$ 个收费站，$m$ 次调整或询问
接下来 $m$ 行，每行将出现以下两种形式中的一种
C l r v 表示将第 $l$ 个收费站到第 $r$ 个收费站之间的所有道路的通行费全部增加 $v$
Q l r 表示对于给定的 $l, r$ ，要求回答小A的问题
所有 C 与 Q 操作中保证 $1 \leq l \leq r \leq n$
输出格式
对于每次询问操作回答一行，输出一个既约分数
若答案为整数 $a$ ，输出 $a/1$
样例输入
4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4
样例输出
1/1
8/3
17/6
数据范围及提示
所有C操作中的 $v$ 的绝对值不超过 $10000$
在任何时刻任意道路的费用均为不超过 $10000$ 的非负整数
对于 $100\%$ 的数据 $n, m \leq 100000$
解题思路
先考虑一段区间 $l$ 到 $r$ 的期望，考虑在一段区间中任意枚举两个点，期望就是
$$
\frac{\sum_{i=l}^r \sum_{j=l}^r w_{i, j}}{{r-l+1 \choose 2}}
$$
分子代表所有可能情况的权值总和，一共有 ${r-l+1 \choose 2}$ 种情况
分母可以 $O(1)$ 求出，问题转化为如何维护分子
我们考虑将每条边编号，原先节点 $1$ 和 $2$ 之间的边编号为 $1$，一次类推，那么 $l$ 到 $r$ 号点实际上对应着 $l$ 到 $r-1$ 号边
所有情况的权值总和还可以用每一条边的权值乘上在路径中的出现次数的和来表示
$$
\sum_{i=l}^{r} v_i \times (r – i + 1) \times (i – l + 1)
$$
暴力拆开
$$
\sum_{i=l}^r v_i \times (r \times i – r \times l + r- i^2 +i \times l – l + 1)
$$
合并变为
$$
(r – l + 1 – r \times l) \sum_{i=l}^r v_i + (r + l) \sum_{i=l}^r v_i \times i – \sum_{i=l}^r v_i i^2
$$
考虑使用线段树维护 $\sum_{i=;}^r v_i$ 和 $\sum_{i=l}^r v_i \times i$ 和 $\sum_{i=l}^r v_i i^2$
在区间加 $k$ 时第一个值需要增加 $(r-l+1) \times k$
第二个值需要增加 $k \times \sum_{i=l}^r i$
第三个值需要增加 $k \times \sum_{i=l}^r i^2$
其中 $\sum_{i=l}^r i$ 和 $\sum_{i=l}^r i^2$ 是定值，可以在线段树建树的时候进行计算
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 100000 + 10;
inline int read(){
int x = 0;
int p = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
p = 0;
ch = getchar();
}
while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}
return p ? x : (-x);
}
namespace SEG{
long long sum1[MAXN << 2], sum2[MAXN << 2], sum3[MAXN << 2], sum4[MAXN << 2], sum5[MAXN << 2];
long long lazy[MAXN << 2];
inline void build(int root, int left, int right){
int lson = root << 1, rson = root << 1 | 1, mid = (left + right) >> 1;
if(left == right){
sum4[root] = left;
sum5[root] = 1LL * left * left;
return;
}
if(left <= mid)
build(lson, left, mid);
if(mid < right)
build(rson, mid+1, right);
sum4[root] = sum4[lson] + sum4[rson];
sum5[root] = sum5[lson] + sum5[rson];
}
inline void pushdown(int root, int left, int right){
if(lazy[root]){
int lson = root << 1, rson = root << 1 | 1, mid = (left + right) >> 1;
sum1[lson] += (mid - left + 1) * lazy[root];
sum2[lson] += sum4[lson] * lazy[root];
sum3[lson] += sum5[lson] * lazy[root];
sum1[rson] += (right - mid) * lazy[root];
sum2[rson] += sum4[rson] * lazy[root];
sum3[rson] += sum5[rson] * lazy[root];
lazy[lson] += lazy[root];
lazy[rson] += lazy[root];
lazy[root] = 0;
}
}
inline void pushup(int root){
int lson = root << 1, rson = root << 1 | 1;
sum1[root] = sum1[lson] + sum1[rson];
sum2[root] = sum2[lson] + sum2[rson];
sum3[root] = sum3[lson] + sum3[rson];
}
inline void update(int root, int left, int right, int qleft, int qright, int k){
int lson = root << 1, rson = root << 1 | 1, mid = (left + right) >> 1;
if(qleft <= left && right <= qright){
sum1[root] += (right - left + 1) * k;
sum2[root] += sum4[root] * k;
sum3[root] += sum5[root] * k;
lazy[root] += k;
return;
}
pushdown(root, left, right);
if(qleft <= mid)
update(lson, left, mid, qleft, qright, k);
if(mid < qright)
update(rson, mid+1, right, qleft, qright, k);
pushup(root);
}
inline void query(int root, int left, int right, int qleft, int qright, long long &res1, long long &res2, long long &res3){
int lson = root << 1, rson = root << 1 | 1, mid = (left + right) >> 1;
if(qleft <= left && right <= qright){
res1 += sum1[root];
res2 += sum2[root];
res3 += sum3[root];
return;
}
pushdown(root, left, right);
if(qleft <= mid)
query(lson, left, mid, qleft, qright, res1, res2, res3);
if(mid < qright)
query(rson, mid+1, right, qleft, qright, res1, res2, res3);
}
}
int n, m;
int main(){
n = read();
m = read();
SEG::build(1, 1, n);
for(register int i=1; i<=m; i++){
char op;
int l, r;
scanf(" %c", &op);
l = read();
r = read() - 1;
if(op == 'C'){
int k = read();
SEG::update(1, 1, n, l, r, k);
}else{
long long tmp1 = 0, tmp2 = 0, tmp3 = 0;
SEG::query(1, 1, n, l, r, tmp1, tmp2, tmp3);
long long ansa = (r - l + 1 - 1LL * r * l) * tmp1 + (r + l) * tmp2 - tmp3;
long long ansb = 1LL * (r - l + 2) * (r - l + 1) / 2;
long long g = __gcd(ansa, ansb);
printf("%lld/%lld\n", ansa / g, ansb / g);
}
}
return 0;
}