题目地址：洛谷：【P2221】[HAOI2012]高速公路 – 洛谷、BZOJ：Problem 2752. — [HAOI2012]高速公路(road)

题目描述

Y901高速公路是一条重要的交通纽带，政府部门建设初期的投入以及使用期间的养护费用都不低，因此政府在这条高速公路上设立了许多收费站。
Y901高速公路是一条由N-1段路以及N个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为1~N，从收费站i行驶到i+1(或从i+1行驶到i)需要收取Vi的费用。高速路刚建成时所有的路段都是免费的。
政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。
无聊的小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<=l<r<=N

输出格式：
对于每次询问操作回答一行，输出一个既约分数
若答案为整数a，输出a/1

输入输出样例

输入样例#1：

4 5
C 1 4 2
C 1 2 -1
Q 1 2
Q 2 4
Q 1 4

输出样例#1：

1/1
8/3
17/6

说明

所有C操作中的v的绝对值不超过10000
在任何时刻任意道路的费用均为不超过10000的非负整数
所有测试点的详细情况如下表所示
Test N M
1 =10 =10
2 =100 =100
3 =1000 =1000
4 =10000 =10000
5 =50000 =50000
6 =60000 =60000
7 =70000 =70000
8 =80000 =80000
9 =90000 =90000
10 =100000 =100000

题解

既然所有情况是等概率的，那么期望可以定义成所有情况的和除以情况数量。我们考虑询问中单独一段路对所有情况的和的贡献，假如为第i段路（即连接第i个与第i+1个收费站的路），则为 (i-l+1)(r-i)v_i ，也就是说，答案是
\begin{aligned} \mathrm{E}(l, r) &= \frac{\sum_{i=l}^{r-1} (i-l+1)(r-i)v_i}{\mathrm{C}_{r-l+1}^2} \\ &= \frac{(r-lr)\sum_{i=l}^{r-1} v_i + (l+r-1) \sum_{i=l}^{r-1} iv_i - \sum_{i=l}^{r-1} i^2v_i}{(r-l)(r-l+1)/2} \end{aligned}
我们考虑用线段树维护v_i, iv_i, i^2v_i的值，每次询问把它们拿出来算一下即可。
当我们使用lazy标记的时候，肯定要求\sum_{i=l}^r i^2的值，平方和公式是\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}，可以做减法求出要求的值。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    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 readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'C' || c == 'Q';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 100005;

inline LL callr(LL l, LL r) {
    return (l + r) * (r - l + 1) / 2;
}

inline LL call2r2(LL l, LL r) {
    return r * (r + 1) * (2 * r + 1) / 6 - l * (l - 1) * (2 * l - 1) / 6;
}

inline LL gcd(LL a, LL b) {
    if(a < b) std::swap(a, b);
    LL t;
    while(b) {
        t = a; a = b; b = t % b;
    }
    return a;
}

#define lch o << 1
#define rch (o << 1) | 1
#define mid ((l + r) >> 1)

struct Node {
    LL v, iv, iiv, add;
} sgt[MAXN << 2];

inline void merge(Node &rt, Node ls, Node rs) {
    rt.v = ls.v + rs.v;
    rt.iv = ls.iv + rs.iv;
    rt.iiv = ls.iiv + rs.iiv;
}

inline void pushdown(int o, int l, int r) {
    if(sgt[o].add) {
        sgt[lch].add += sgt[o].add;
        sgt[rch].add += sgt[o].add;
        sgt[lch].v += sgt[o].add * (mid - l + 1);
        sgt[rch].v += sgt[o].add * (r - mid);
        sgt[lch].iv += sgt[o].add * callr(l, mid);
        sgt[rch].iv += sgt[o].add * callr(mid + 1, r);
        sgt[lch].iiv += sgt[o].add * call2r2(l, mid);
        sgt[rch].iiv += sgt[o].add * call2r2(mid + 1, r);
        sgt[o].add = 0;
    }
}

inline void add(int o, int l, int r, int ll, int rr, LL v) {
    if(l >= ll && r <= rr) {
        sgt[o].add += v;
        sgt[o].v += v * (r - l + 1);
        sgt[o].iv += v * callr(l, r);
        sgt[o].iiv += v * call2r2(l, r);
        return;
    }
    pushdown(o, l, r);
    if(ll <= mid) add(lch, l, mid, ll, rr, v);
    if(rr > mid) add(rch, mid + 1, r, ll, rr, v);
    merge(sgt[o], sgt[lch], sgt[rch]);
}

inline Node query(int o, int l, int r, int ll, int rr) {
    if(l == ll && r == rr) {
        return sgt[o];
    }
    pushdown(o, l, r);
    if(rr <= mid) {
        return query(lch, l, mid, ll, rr);
    } else if(ll > mid) {
        return query(rch, mid + 1, r, ll, rr);
    } else {
        Node res, ls = query(lch, l, mid, ll, mid), 
            rs = query(rch, mid + 1, r, mid + 1, rr);
        merge(res, ls, rs);
        return res;
    }
}

LL n, m, l, r, v;
char op;

int main() {
    n = readint(); m = readint();
    while(m--) {
        op = readop(); l = readint(); r = readint();
        if(op == 'C') {
            v = readint();
            add(1, 1, n - 1, l, r - 1, v);
        } else {
            Node res = query(1, 1, n - 1, l, r - 1);
            LL a = (r - l * r) * res.v + (l + r - 1) * res.iv - res.iiv,
                b = (r - l) * (r - l + 1) / 2, g = gcd(a, b);
            printf("%lld/%lld\n", a / g, b / g);
        }
    }
    return 0;
}