自分用です。詳しいことは何一つ書いてアランです。
左右に高さ0のW個のマスがあり、ここN個のl_i番目からr_i番目のマスをちょうど覆うように高さ1のレンガを順に積んでいき、最終的なレンガの上面の高さを求める問題。
区間に対する処理なので普通にセグ木で解こうかと思った。
解説によると遅延評価セグ木を使うと長さWの配列1回につきO(logW)で解けるらしい。
遅延評価セグ木は主に
・配列のある区間をxに更新(update)/xを加算(add)
・配列のある区間の最小値・最大値・合計などを求める。
をO(logW)で処理できるらしい。
もーちょい詳しく見てみたいので以下のサイトを訪問。
普通のセグ木は値が加算されると上のノードまでどんどん伝搬させていくが、遅延評価はそれをクエリでそのノードにアクセスしたときまでその更新をサボることで範囲の長さLのとき、O(LlogN)かかる処理をO(logN)にできるらしい。賢い。
あらかた理解したため実装。
初期化のときに遅延配列の宣言をして、評価・加算などの処理で遅延配列に対して処理をするらしいが・・・
書いたことないことを理由に思考をサボり、解説をパクる。
遅延評価セグ木も更新をサボっているため、これで対等。
class segment_tree{
private:
int sz;
std::vector<int> seg;
std::vector<int> lazy;
void push(int k){
if(k < sz){
lazy[k*2] = max(lazy[k*2], lazy[k]);
lazy[k*2 + 1] = max(lazy[k*2 + 1], lazy[k]);
}
seg[k] = max(seg[k], lazy[k]);
lazy[k] = 0;
}
void update(int a, int b, int x, int k, int l, int r){
push(k);
if(r <= a || b <= l)return;
if(a <= l && r <= b){
lazy[k] = x;
push(k);
return;
}
update(a, b, x, k * 2, l, (l+r) >> 1);
update(a, b, x, k * 2 + 1, (l+r) >> 1, r);
seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
}
int range_max(int a, int b, int k, int l, int r){
push(k);
if(r <= a || b <= l)return 0;
if(a <= l && r <= b)return seg[k];
int lc = range_max(a, b, k * 2, l, (l + r) >> 1);
int rc = range_max(a, b, k * 2 + 1, (l + r) >> 1, r);
return max(lc, rc);
}
public:
segment_tree() : sz(0), seg(), lazy() {};
segment_tree(int N) {
sz = 1;
while(sz < N) {
sz *= 2;
}
seg = std::vector<int>(sz * 2, 0);
lazy = std::vector<int>(sz * 2, 0);
}
void update(int l, int r, int x) {
update(l, r, x, 1, 0, sz);
}
int range_max(int l, int r) {
return range_max(l, r, 1, 0, sz);
}
};
以上、丸パクリさせていただいた。
ところで、「：」がついたコンストラクタは初期化子リストと言われるもので、変数名(初期化)で書くらしい。
普通にコンストラクタを書くより、効率的 & const変数の初期化ができるので優秀らしい。
(コンストラクタ内に書くやり方は初期化ではなく代入で、しれっと初めに各クラスのデフォルトコンストラクタで初期化されていることにより初期化＋代入という二度手間が発生しているため)
ということで、29問目、無事AC
丸パクリしたことにより、応用出来るかは不安。
ところで、作用素が可換か、非可換かなどで、処理が変わるなど、遅延セグ木には注意するところが割と多いんだそう。
遅延セグ木に限ったことじゃないけど、Pythonなどインタプリタ言語では非再帰のほうが高速だよね。とかも。
具体的には以下を参照
この辺は抽象化するときにでも詳しく見ることにする。
以下、抽象化するとき用