BZOJ 2752: [HAOI2012]高速公路(road)

这题应该不算严格的概率题。。
只是把总长度/方案数而已。。
根据期望可加(其实也可以就只是考虑每个收费站对答案的贡献)我们可以考虑对于每个收费站的期望 然后加起来
对于一个l~r之间的收费站i 对答案的贡献是(i – l + 1) * (r – i) * vi
把它化开 发现只要用线段树维护Σvi、Σi*vi、Σi*i*vi即可

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

struct node
{
  ll sum, sum1, sum2, lazy;
}t[maxn * 4];

ll sum[maxn], sum2[maxn], n, m;

void lazy(ll now, ll l, ll r)
{
  if (!t[now].lazy) return;
  ll p = t[now].lazy;
  t[now].lazy = 0;
  t[now].sum += (r - l + 1) * p;
  t[now].sum1 += (sum[r] - sum[l - 1]) * p;
  t[now].sum2 += (sum2[r] - sum2[l - 1]) * p;
  if (l == r) return;
  t[now * 2].lazy += p;
  t[now * 2 + 1].lazy += p;
}

void modify(ll l, ll r, ll now, ll lf, ll rt, ll v)
{
  lazy(now, l, r);
  if (l >= lf && r <= rt)
  {
    t[now].lazy += v;
    return;
  }
  ll mid = (l + r) / 2;
  if (lf <= mid) modify(l, mid, now * 2, lf, rt, v);
  if (rt >= mid + 1) modify(mid + 1, r, now * 2 + 1, lf, rt, v);
  lazy(now * 2, l, mid);
  lazy(now * 2 + 1, mid + 1, r);
  t[now].sum = t[now * 2].sum + t[now * 2 + 1].sum;
  t[now].sum1 = t[now * 2].sum1 + t[now * 2 + 1].sum1;
  t[now].sum2 = t[now * 2].sum2 + t[now * 2 + 1].sum2;
}

ll query(ll l, ll r, ll now, ll lf, ll rt)
{
  lazy(now, l, r);
  if (l >= lf && r <= rt) return (rt + lf - 1) * t[now].sum1 - t[now].sum2 - (lf * rt - rt) * t[now].sum;
  ll mid = (l + r) / 2, ans = 0;
  if (lf <= mid) ans += query(l, mid, now * 2, lf, rt);
  if (rt >= mid + 1) ans += query(mid + 1, r, now * 2 + 1, lf, rt);
  return ans;
}

ll gcd(ll a, ll b)
{
  return (!b) ? a : gcd(b, a % b);
}

int main()
{
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
  scanf("%lld%lld", &n, &m);
  for (ll i = 1; i <= n; ++i)
    sum[i] = sum[i - 1] + i, sum2[i] = sum2[i - 1] + (ll)i * i;
  for (ll i = 0; i < m; ++i)
  {
    char c;
    ll l, r;
    scanf("\n%c%lld%lld", &c, &l, &r);
    if (c == 'C')
    {
      ll v;
      scanf("%lld", &v);
      modify(1, n, 1, l, r - 1, v);
    }
    else
    {
      ll t = query(1, n, 1, l, r), k = (1 + (r - l)) * (r - l) / 2;
      ll g = gcd(t, k);
      printf("%lld/%lld\n", t / g, k / g);
    }
  }
  fclose(stdin);fclose(stdout);
}