Luogu P2221 [HAOI2012] 高速公路

qwq

假期望题,分母显然为 $C_{R - L + 1}^2$.把区间内所有子段的和求出来就完事了。

然后考虑线段树区间合并,似乎不可做。

这时SX红太阳郭老师开导了我,我们可以采取类似于树上染色的思路,考虑每条边可以被经过几次。

这就比较显然了,为$(R - i + 1)(i - L + 1)$.那么分子就是$\sum \limits _{i = L} ^ R (R - i + 1)(i - L + 1) w_i$.

化简一下就是 $\sum \limits _{i = L} ^ R (R - L + 1 - LR)w_i + (L + R) i w_i - i^2 w_i$.

线段树记3个tag:$s_1 = w_i, s_2 = i w_i, s_3 = i^2 w_i$.

区间合并直接加起来。

再考虑修改边权,就是加个 $v (R - L + 1 - LR)$ $v (L + R) \sum i$ 和 $ -v i ^2$.

再记$s_4 = \sum i, s_5 = \sum i^2$.

这道题就完了。

注意坑点:

  1. 给的是点,我们维护的是线段,需要处理一下
  2. 能开 long long 就开 long long !!别吝啬!! 如果你WA20了,大约就是该开的long long没开
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
#include <bits/stdc++.h>
#define ll long long

const int N = 100000 + 233;
ll n, m, sum[5];
char opt[5];
struct SegTree {
ll l, r, s[8], tag;
} t[N << 2];

inline void Pushup(ll p) {
for (int i = 1; i <= 3; i++) t[p].s[i] = t[p << 1].s[i] + t[p << 1 | 1].s[i];
}

ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y); }

void Build(ll p, ll l, ll r) {
t[p].l = l, t[p].r = r;
if (l == r) return (void)(t[p].s[4] = l, t[p].s[5] = l * l);
ll mid = (l + r) >> 1;
Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r);
for (int i = 4; i <= 5; i++) t[p].s[i] = t[p << 1].s[i] + t[p << 1 | 1].s[i];
}

inline void Add(ll p, ll k) {
t[p].s[1] += (t[p].r - t[p].l + 1) * k;
t[p].s[2] += k * t[p].s[4];
t[p].s[3] += k * t[p].s[5];
t[p].tag += k;
}

inline void Pushdown(ll p) {
Add(p << 1, t[p].tag), Add(p << 1 | 1, t[p].tag);
t[p].tag = 0;
}

void Change(ll p, ll l, ll r, ll v) {
if (l <= t[p].l && r >= t[p].r) return (void)Add(p, v);
ll mid = (t[p].l + t[p].r) >> 1;
if (t[p].tag) Pushdown(p);
if (l <= mid) Change(p << 1, l, r, v);
if (r > mid) Change(p << 1 | 1, l, r, v);
Pushup(p);
}

void Ask(ll p, ll l, ll r) {
if (l <= t[p].l && r >= t[p].r) {
for (int i = 1; i <= 3; i++) sum[i] += t[p].s[i];
return;
}
ll mid = (t[p].l + t[p].r) >> 1;
if (t[p].tag) Pushdown(p);
if (l <= mid) Ask(p << 1, l, r);
if (r > mid) Ask(p << 1 | 1, l, r);
}

inline void print(ll x, ll y) {
ll g = gcd(x, y);
printf("%lld/%lld\n", x / g, y / g);
}

signed main() {
scanf("%lld%lld", &n, &m);
Build(1, 1, n);
for (ll i = 1, l, r; i <= m; i++) {
ll v;
scanf("%s%lld%lld", opt, &l, &r);
r--;
if (opt[0] == 'C') {
scanf("%lld", &v), Change(1, l, r, v);
} else {
sum[1] = sum[2] = sum[3] = 0;
Ask(1, l, r);
ll a = (r - l + 1 - l * r) * sum[1] + (r + l) * sum[2] - sum[3];
ll b = (r - l + 2) * (r - l + 1) / 2;
print(a, b);
}
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×