セグメントツリーの使い方
アドホックな演算子・作用素とかのまとめ.
セグ木コン
頂点ごとに別の値を K 回加算
遅延セグ木
seg[i] <- seg[i] + k * c[i] という演算を区間に対して行う.
累積和を取ると区間ごとにまとめて加算できるようになる.
Euler-Tour をすると潜る際に重みを割り当て,戻る際に重みの加法逆元($ -1倍)を割り当てるが,部分木加算クエリをするときに足すものと引くものが存在する.
そこで潜る際のほうをc[i] = 1として,戻る際のほうをc[i] = -1とすれば達成できる.
code:cpp
auto g = [](i64 data, i64 lazy, int l, int r) -> i64 {
return (sr - sl) * lazy + data; }
// 作用素どうしのマージは普通に加算
auto h = [](i64 a, i64 b) { return a + b; }
マージの際に端点同士から定まるコストが加わる
隣接する頂点をマージする演算?
頂点に値が加算される
辺のコスト + 端点のコストがコストだが K の倍数のときは 0 になる
辺の情報は map などを用いると楽
code:cpp
auto f = &(node a, node b) { if(a.r == -1) return b;
if(b.l == -1) return a;
if(!(val % k)) val = 0;
return node(a.l, b.r, a.val + val + b.val);
};