Submission #64223

ソースコード

?
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
212
213
#include <iostream>
#include <vector>
using namespace std;
#define int long long
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 15:00:41
言語 C++17
状態 Accepted
得点 6
ソースコード長 5310 Byte
最大実行時間 282 ms
最大メモリ使用量 81000 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 27 ms 600 KB
1
in02.txt AC 32 ms 660 KB
1
in03.txt AC 105 ms 9040 KB
1
in04.txt AC 134 ms 30156 KB
1
in05.txt AC 252 ms 33176 KB
1
in06.txt AC 241 ms 35036 KB
1
in07.txt AC 232 ms 37032 KB
1
in08.txt AC 224 ms 39020 KB
1
in09.txt AC 186 ms 41388 KB
1
in10.txt AC 197 ms 43288 KB
1
in11.txt AC 198 ms 45060 KB
1
in12.txt AC 187 ms 46964 KB
1
in13.txt AC 133 ms 32612 KB
1
in14.txt AC 91 ms 39640 KB
1
in15.txt AC 282 ms 56516 KB
1
in16.txt AC 194 ms 61404 KB
1
in17.txt AC 232 ms 62704 KB
1
in18.txt AC 229 ms 67704 KB
1
in19.txt AC 263 ms 69560 KB
1
in20.txt AC 179 ms 71544 KB
1
in21.txt AC 215 ms 63408 KB
1
in22.txt AC 233 ms 65428 KB
1
in23.txt AC 207 ms 67456 KB
1
in24.txt AC 216 ms 69224 KB
1
in25.txt AC 230 ms 70100 KB
1
in26.txt AC 103 ms 43304 KB
1
in27.txt AC 43 ms 44404 KB
1
in28.txt AC 19 ms 44484 KB
1
in29.txt AC 51 ms 46236 KB
1
in30.txt AC 55 ms 48236 KB
1
in31.txt AC 234 ms 79144 KB
1
in32.txt AC 218 ms 81000 KB
1
sample01.txt AC 18 ms 52284 KB
1
sample02.txt AC 29 ms 52244 KB
1