Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP4927 [1007]梦美与线段树

Posted on In
Symbols count in article: 3.3k Reading time ≈ 3 mins.

出题人我谢谢您

梦美与线段树

很快手玩了一下答案，设 $\{a_i\}$ 为序列， $\{v_i\}$ 为线段树节点的权值，答案就是 $Ans = \frac{\sum v_i^2}{\sum a_i}$

下面的分母好解决，问题在上面的平方和

考虑线段树维护节点权值平方和（同时可以很自然的维护序列和），当区间加 $d$ 的时候，设该节点对应区间长度为 $len_i$ ，则 $v_i^2 \rightarrow (v_i + len_i * d)^2 = v_i^2 + v_i * len_i * 2d + len_i^2 * d$ ，发现节点的改变量和它的权值与长度都有关，考虑维护系数，即维护 $v_i * len_i$ 的和与 $len_i^2$ 和

具体地，设 $s2$ 表示节点权值示平方和， $sl2$ 表示节点长度平方和（它只用算一次，是不变的）， $sm$ 是 $v_i * len_i$ 的和有：
$$
\begin{aligned}
pushup : \\
& v_i = v_{lc} + v_{rc} \\
& s2_i = v_i^2 + s2_{lc} + s2_{rc} \\
& sl2_i = len_i^2 + sl2_{lc} + sl2_{rc} \\
& sm_i = len_i * v_i + sm_{lc} + sm_{rc} \\
pushdown : \\
& s2_i = sl2_i * d^2 + 2d * sm_i + s2_i \\
& v_i = len_i * d + v_i \\
& sm_i = sl2_i * d + sm_i \\
\end{aligned}
$$
打好懒标记，调了一下，一交……WA90？！

一看，输出了个 $0$ 以为爆精度了，就 #define int long long 结果不变，一看讨论区，有人说这题要用高精（或者不要脸的 __int128 ），我看了一遍，每一步都模了 $P = 998244353$ ，连 long long 会不会炸都怀疑，但还是改成 __int128 试了试，结果不变……

对 __int128 不是很熟悉，我以为自己用错了，还手打了快读快输，结果还是不变

忍无可忍看题解，发现问题在于题目说“令答案化成最简分数为 $\frac{p}{q}$ （保证 $q$ 不是 $998244353$ 的倍数”，也就是说答案可能是 $\frac{k * P}{r * P}$ 的形式，所以中间的过程中不能取模，只能开 __int128 硬存最后约分

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
#include <bits/stdc++.h>
#define int __int128
#define gh() getchar()
using namespace std;
const int N = 1e5 + 5, P = 998244353;
int n, m;
int a[N];
struct LineTree
{
    int l, r;
    //值,平方和,长度平方和,长度与值的积的和
    int v, s2, sl2, sm;
    int add;
#define l(x) tr[(x)].l
#define r(x) tr[(x)].r
#define v(x) tr[(x)].v
#define s2(x) tr[(x)].s2
#define sl2(x) tr[(x)].sl2
#define sm(x) tr[(x)].sm
#define ad(x) tr[(x)].add
#define lc (u << 1)
#define rc (u << 1 | 1)
#define Mid (tr[u].l + tr[u].r >> 1)
} tr[N << 2];
void read(int &x)
{
    x = 0;
    char ch = gh(), t = 0;
    while (ch < '0' || ch > '9')
        t |= ch == '-', ch = gh();
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch - 48, ch = gh();
    if (t)
        x = -x;
}
void write(int x)
{
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
int qpow(int x, int y)
{
    int res = 1;
    while (y)
    {
        if (y & 1)
            res = res * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return res;
}
void push_init(int u)
{
    int len = r(u) - l(u) + 1;
    v(u) = (v(lc) + v(rc));
    s2(u) = (v(u) * v(u) + s2(lc) + s2(rc));
    sl2(u) = (len * len + sl2(lc) + sl2(rc));
    sm(u) = ((r(u) - l(u) + 1) * v(u)+ sm(lc) + sm(rc));
}
void push_up(int u)
{
    v(u) = (v(lc) + v(rc));
    s2(u) = (v(u) * v(u) + s2(lc) + s2(rc));
    sm(u) = ((r(u) - l(u) + 1) * v(u) + sm(lc) + sm(rc));
}
void add_tag(int u, int d)
{
    s2(u) = (sl2(u) * d * d +d * 2 * sm(u) + s2(u));
    v(u) = ((r(u) - l(u) + 1) * d + v(u));
    sm(u) = (sl2(u) * d + sm(u));
    ad(u) = (ad(u) + d);
}
void push_down(int u)
{
    if (ad(u))
    {
        add_tag(lc, ad(u));
        add_tag(rc, ad(u));
        ad(u) = 0;
    }
}
void build(int u, int l, int r)
{
    l(u) = l, r(u) = r;
    if (l == r)
    {
        v(u) = sm(u) = a[l];
        s2(u) = a[l] * a[l];
        sl2(u) = 1;
        return ;
    }
    int mid = Mid;
    build(lc, l, mid), build(rc, mid + 1, r);
    push_init(u);
}
void modify(int u, int l, int r, int d)
{
    if (l(u) >= l && r(u) <= r)
        return add_tag(u, d);
    push_down(u);
    int mid = Mid;
    if (l <= mid)
        modify(lc, l, r, d);
    if (r > mid)
        modify(rc, l, r, d);
    push_up(u);
}
int ask()
{
    int t = __gcd(s2(1), v(1));
    int A = s2(1) / t, B = v(1) / t;
    return A % P * qpow(B, P - 2) % P;
}
signed main()
{
    read(n), read(m);
    for (int i = 1; i <= n; ++i)
        read(a[i]);
    build(1, 1, n);
    int op, l, r, v;
    while (m--)
    {
        read(op);
        if (op == 1)
        {
            read(l), read(r), read(v);
            modify(1, l, r, v);   
        }
        else
            write(ask()), putchar('\n');
    }
    return 0;
}