セグメント木とNoelちゃんの旅行(yukicoder 631)

No.631 Noelちゃんと電車旅行 - yukicoder

今日一日この問題で頭と時間を溶かしましたが、この問題...

セグメント木の勉強にとっても役に立つ良問でした!!!!(Noelちゃん流石)

解説というかどんなふうに考えていったか書き記そうと思います

セグメント木ってなんなの?

hogecoder-セグメント木をソラで書きたいあなたに

このブログすごい読みやすい！必見...

これを読みつつグラフを書いてみたりして、理解した今のイメージを書いていきます(個人的な意見です)

セグメント木も結局グラフ

グラフは大雑把に言うとノードとノードの関係を表したものですよね

例えばダイクストラ法などを使う問題の場合、

ノードとノードのコストの関係が大切ですよね

セグメント木では親と子の関係を考えるのが大切です

それによっては色々な問題が解くことができるそうです(強い)

和であれば、任意の区間の和が計算でき

大きい方であれば、任意の区間の最大値を計算できます

しかも高速で....

遅延評価セグメント木

"ただの"セグメント木だと、

区間に対してのノードの変更に変更するノードの個数の分だけ時間がかかってしまいます

ここで、後から区間への変更を評価することによって、高速化するという遅延評価セグメントというものが存在します

頼ります

hogecoder-遅延評価セグメント木をソラで書きたいあなたに

どうやって考えるかはNoelちゃんの旅行で実際にしてみます

No.631 Noelちゃんと電車旅行

駅の番号が1始まりですが、0~N-1というふうにします

まず、方針としては

駅iで止まるとき、Noelちゃんの旅行は T[i] + 3 *(N - i)分かかる
これらの最大値を求める

といったところです

出ました最大値。これを求めるセグメント木を作るわけです

また、始発に遅延が生じる区間があるわけです

今回遅延はT[i]に足していくので

区間に足していく遅延評価セグメント木を作るということになります

じゃあどうやって作るか

ノードとノードの関係

最大値を求めるので今回は大きい方の値を取ることになります

node[k] = max(node[2 * k + 1] , node[2 * k + 2]);

という感じですね

求めたい値

0~N-2の区間にあるノードのうちの最大値ですね

上のブログのように再帰で簡単にできます

遅延評価の仕方

j回目の始発遅延によって、L[j]からR[j]の始発がD[j]分遅れます

つまり区間L[j]~R[j]に対してD[j]を加算するわけです

区間の和を求めるときは紹介したブログのように、数を分けるようにして子のノードに遅延評価する値を渡していました

ですが、今回は最大値です。なので、素直にすべての区間内にあるノードの遅延評価する値を代入していけばよいです

void eval(int k,int l,int r)
{
    if(lazy[k] != 0)
    {
        node[k] += lazy[k];
        if(r - l > 1)
        {
            //そのまま渡していく
            lazy[2 * k + 1] += lazy[k];
            lazy[2 * k + 2] += lazy[k];
        }
        lazy[k] = 0;
    }
}
void add(int a,int b,ll x,int k = 0,int l = 0,int r = -1)
{
    if(r < 0) r = n;
    eval(k,l,r);
    if(r <= a || b <= l) return;
    if(a <= l && r <= b)
    {
        //ここもそのまま足す
        lazy[k] += x;
        eval(k,l,r);
    }
    else
    {
        add(a,b,x,2 * k + 1,l,(l + r) / 2);
        add(a,b,x,2 * k + 2,(l + r) / 2,r);
        node[k] = max(node[2 * k + 1] , node[2 * k + 2]);
    }
}

こんな感じで

これらの要素が揃っていればおおよそ解けるという感じですね

僕のコードはこれ https://yukicoder.me/submissions/228221

相変わらず説明が下手...

とりあえず作り方を色々勉強すれば成長できそう

最後に

すっごく...Noelちゃんでした...