For this problem http://www.usaco.org/index.php?page=viewproblem2&cpid=973, it appeared in the Range Updates Range Query module. However, after reading the solution, it appears to be 2 BITs instead of a Lazy SegTree. I wonder what is the Lazy Segtree solution to this problem? Or is the idea to substitute the BIT with a Lazy Segtree?
Good question. If we introduce an additional array arr
where arr[i]
denotes the colorfulness of snowball i
, we can replace this function in the analysis:
void upd(int x, int y) {
A.upd(st[x],y); A.upd(en[x]+1,-y);
B.upd(st[x],y*sub[x]);
}
with
void upd() {
for (int i = st[x]; i <= en[x]; ++i) arr[i] += y;
}
and
cout << sub[x]*A.sum(st[x])+B.query(st[x]+1,en[x]) << "\n";.
with
ll sum = 0;
for (int i = st[x]; i <= en[x]; ++i) sum += arr[i];
cout << sum << "\n";
Any data structure that supports range increment range sum on arr
will suffice. Let me know if that made sense.
Yes, that makes sense. Thank you.