Luckyleaves's Blog

stay hungry,stay foolish greedy and lucky

P4927 梦美与线段树

联赛之后连裸的线段树模板都打得如此痛苦。

自闭了,$QWQ$

Solution

  • 首先考虑三个点的情况

无标题.png

  • 不难发现此时答案为:$v_{fa} * 1 + v_{s1} * \frac{v_{s1}}{v_{fa}} + v_{s2} * \frac{v_{s2}}{v_{fa}} = \frac{v_{fa}^2 + v_{s1}^2 + v_{s2}^2}{v_{fa}}$,这时我们再将三个点上推到所有情况,设每个单点的答案为 $w$,可得

$$
w_{fa} = \frac {\sum v_{son}^2 + v_{fa}^2}{v_{fa}}
$$

  • 再考虑懒标记下传的情况,具体地,设 $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}
    $$

  • 然后你一交,就 $WA$ 了。

  • 在评论区游走了许久,才发现在不约分的情况下,$q$ 可能是 $mod$ 的倍数,所以一模答案就会变成0,而且答案可能在中途爆 $long \ long$ 所以我们直接手写高精($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
136
137
138
139
140
141
142
143
#include<bits/stdc++.h>
#define LL long long
#define l(x) x << 1
#define r(x) x << 1 | 1
#define LL __int128
using namespace std;
const int N = 1e5 + 5, mod = 998244353;
template <class T>
inline void read(T& res)
{
res = 0; bool flag = 0;
char c = getchar();
while(c < '0' || c > '9'){if(c == '-') flag = 1; c = getchar();}
while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + c - '0', c = getchar();
if(flag) res = -res;
}
struct Node{
int l, r;
LL v, flag, len;
LL sum;
LL num;
}tr[N << 2];
int n, m;
LL a[N];
LL qpow(LL x, LL k)
{
LL res = 1;
while(k)
{
if(k & 1) res = (res * x) % mod;
k >>= 1;
x = (x * x) % mod;
}
return res;
}
namespace pol
{
void pushup(int x)
{
LL len = tr[x].r - tr[x].l + 1;
tr[x].sum = (tr[l(x)].sum + tr[r(x)].sum);
tr[x].num = (tr[l(x)].num + tr[r(x)].num + tr[x].sum * tr[x].sum);
tr[x].v = (tr[l(x)].v + tr[r(x)].v + len * tr[x].sum);
tr[x].len = (tr[l(x)].len + tr[r(x)].len + len * len);
}
}
namespace emb
{
void pushup(int x)
{
LL len = tr[x].r - tr[x].l + 1;
tr[x].sum = (tr[l(x)].sum + tr[r(x)].sum);
tr[x].num = (tr[l(x)].num + tr[r(x)].num + tr[x].sum * tr[x].sum);
tr[x].v = (tr[l(x)].v + tr[r(x)].v + len * tr[x].sum);
}
}
void add(int x, LL w)
{
LL len = tr[x].r - tr[x].l + 1;
tr[x].num = ((tr[x].len * w * w + 2 * w * tr[x].v) + tr[x].num);
tr[x].flag = (tr[x].flag + w);
tr[x].sum = (tr[x].sum + w * len);
tr[x].v = (tr[x].len * w + tr[x].v);
}
void pushdown(int x)
{
if(tr[x].flag)
{
add(l(x), tr[x].flag);
add(r(x), tr[x].flag);
tr[x].flag = 0;
}
}
void build(int x, int l, int r)
{
if(l == r)
{
tr[x].sum = a[l];
tr[x].l = tr[x].r = l;
tr[x].num = a[l] * a[l];
tr[x].v = a[l];
tr[x].len = 1;
return ;
}
tr[x].l = l, tr[x].r = r;
int mid = l + r >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
pol:: pushup(x);
}
void modify(int x, int l, int r, LL w)
{
if(l <= tr[x].l && tr[x].r <= r)
{
add(x, w);
return ;
}
pushdown(x);
int mid = tr[x].l + tr[x].r >> 1;
if(l <= mid) modify(x << 1, l, r, w);
if(r > mid) modify(x << 1 | 1, l, r, w);
emb:: pushup(x);
}
LL gcd(LL x, LL y)
{
return y ? gcd(y, x % y) : x;
}
LL ask()
{
LL t = gcd(tr[1].sum, tr[1].num);
LL x1 = tr[1].num / t;
LL x2 = tr[1].sum / t;
return x1 % mod * qpow(x2, mod - 2) % mod;
}
void write(LL x)
{
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int main()
{
read(n), read(m);
for(int i = 1;i <= n;i ++) read(a[i]);
build(1, 1, n);
while(m --)
{
int op;
read(op);
if(op == 2)
{
write((ask() + mod) % mod);
puts("");
}
if(op == 1)
{
int l, r;
LL w;
read(l), read(r), read(w);
modify(1, l, r, w);
}
}
return 0;
}