Submission #64218

ソースコード

?
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <iostream>
#include <vector>
using namespace std;
template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H >
struct LazySegmentTree {
int sz, height;
vector< Monoid > data;
vector< OperatorMonoid > lazy;
const F f;
const G g;
const H h;
const Monoid M1;
const OperatorMonoid OM0;
LazySegmentTree(int n, const F f, const G g, const H h,
const Monoid &M1, const OperatorMonoid OM0)
: f(f), g(g), h(h), M1(M1), OM0(OM0) {
sz = 1;
height = 0;
while(sz < n) sz <<= 1, height++;
data.assign(2 * sz, M1);
lazy.assign(2 * sz, OM0);
}
void set(int k, const Monoid &x) {
data[k + sz] = x;
}
void build() {
for(int k = sz - 1; k > 0; k--) {
data[k] = f(data[2 * k + 0], data[2 * k + 1]);
}
}
inline void propagate(int k) {
if(lazy[k] != OM0) {
lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
data[k] = apply(k);
lazy[k] = OM0;
}
}
inline Monoid apply(int k) {
return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]);
}
inline void recalc(int k) {
while(k >>= 1) data[k] = f(apply(2 * k + 0), apply(2 * k + 1));
}
inline void thrust(int k) {
for(int i = height; i > 0; i--) propagate(k >> i);
}
void update(int a, int b, const OperatorMonoid &x) {
if(a >= b) return;
thrust(a += sz);
thrust(b += sz - 1);
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) lazy[l] = h(lazy[l], x), ++l;
if(r & 1) --r, lazy[r] = h(lazy[r], x);
}
recalc(a);
recalc(b);
}
Monoid query(int a, int b) {
if(a >= b) return M1;
thrust(a += sz);
thrust(b += sz - 1);
Monoid L = M1, R = M1;
for(int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if(l & 1) L = f(L, apply(l++));
if(r & 1) R = f(apply(--r), R);
}
return f(L, R);
}
Monoid operator[](const int &k) {
return query(k, k + 1);
}
template< typename C >
int find_subtree(int a, const C &check, Monoid &M, bool type) {
while(a < sz) {
propagate(a);
Monoid nxt = type ? f(apply(2 * a + type), M) : f(M, apply(2 * a + type));
if(check(nxt)) a = 2 * a + type;
else M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template< typename C >
int find_first(int a, const C &check) {
Monoid L = M1;
if(a <= 0) {
if(check(f(L, apply(1)))) return find_subtree(1, check, L, false);
return -1;
}
thrust(a + sz);
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
if(a & 1) {
Monoid nxt = f(L, apply(a));
if(check(nxt)) return find_subtree(a, check, L, false);
L = nxt;
++a;
}
}
return -1;
}
template< typename C >
int find_last(int b, const C &check) {
Monoid R = M1;
if(b >= sz) {
if(check(f(apply(1), R))) return find_subtree(1, check, R, true);
return -1;
}
thrust(b + sz - 1);
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1) {
if(b & 1) {
Monoid nxt = f(apply(--b), R);
if(check(nxt)) return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
template< typename Monoid, typename OperatorMonoid, typename F, typename G, typename H >
LazySegmentTree< Monoid, OperatorMonoid, F, G, H > get_lazy_segment_tree
(int N, const F &f, const G &g, const H &h, const Monoid &M1, const OperatorMonoid &OM0) {
return {N, f, g, h, M1, OM0};
}
constexpr int MOD = 998244353;
vector<vector<int> > graph;
vector<int> v, depth;
vector<pair<int, int> > sec;
void dfs(int now, int par, int dep){
sec[now].first = v.size();
sec[now].second = v.size() + 1;
v.emplace_back(now);
depth[now] = dep;
for(auto e : graph[now]){
if(e != par){
dfs(e, now, dep + 1);
sec[now].second = v.size();
}
}
return;
}
signed main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, q;
cin >> n >> q;
graph.resize(n);
sec.resize(n);
depth.resize(n);
auto f = [](auto a, auto b){
return (pair<long long, long long>{(a.first + b.first) % MOD, (a.second + b.second) % MOD});
};
auto g = [](auto a, auto b){
return (pair<long long, long long>{(a.first + a.second * b) % MOD, a.second});
};
auto h = [](auto a, auto b){
return ((a + b) % MOD);
};
auto seg = get_lazy_segment_tree(n, f, g, h, pair<long long, long long>{0LL, 0LL}, 0);
for(int i = 0; i < n-1; ++i){
int a, b;
cin >> a >> b;
--a, --b;
graph[a].emplace_back(b);
graph[b].emplace_back(a);
}
dfs(0, -1, 1);
for(int i = 0; i < n; ++i){
seg.set(i, make_pair(0LL, depth[v[i]]));
}
seg.build();
for(int i = 0; i < q; ++i){
int x, v;
cin >> x >> v;
--x;
seg.update(sec[x].first, sec[x].second, v);
cout << seg.query(0, n).first << '\n';
}
return (0);
}

ステータス

項目 データ
問題 1412 - RAQ on Tree
ユーザー名 ei1903
投稿日時 2020-10-03 14:31:15
言語 C++17
状態 Accepted
得点 6
ソースコード長 5285 Byte
最大実行時間 310 ms
最大メモリ使用量 76684 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 27 ms 604 KB
1
in02.txt AC 21 ms 664 KB
1
in03.txt AC 111 ms 8020 KB
1
in04.txt AC 133 ms 26156 KB
1
in05.txt AC 222 ms 29088 KB
1
in06.txt AC 251 ms 30984 KB
1
in07.txt AC 247 ms 32872 KB
1
in08.txt AC 230 ms 34896 KB
1
in09.txt AC 178 ms 37428 KB
1
in10.txt AC 178 ms 39264 KB
1
in11.txt AC 190 ms 41236 KB
1
in12.txt AC 206 ms 43208 KB
1
in13.txt AC 133 ms 31100 KB
1
in14.txt AC 78 ms 37928 KB
1
in15.txt AC 284 ms 53364 KB
1
in16.txt AC 202 ms 58184 KB
1
in17.txt AC 242 ms 59540 KB
1
in18.txt AC 217 ms 64588 KB
1
in19.txt AC 310 ms 66500 KB
1
in20.txt AC 185 ms 68540 KB
1
in21.txt AC 226 ms 58036 KB
1
in22.txt AC 233 ms 59892 KB
1
in23.txt AC 188 ms 61756 KB
1
in24.txt AC 205 ms 63744 KB
1
in25.txt AC 228 ms 65984 KB
1
in26.txt AC 63 ms 43184 KB
1
in27.txt AC 49 ms 44412 KB
1
in28.txt AC 20 ms 44364 KB
1
in29.txt AC 57 ms 46240 KB
1
in30.txt AC 60 ms 48236 KB
1
in31.txt AC 230 ms 74792 KB
1
in32.txt AC 217 ms 76684 KB
1
sample01.txt AC 27 ms 52092 KB
1
sample02.txt AC 21 ms 52176 KB
1