tomboのブログ

競技プログラミングのことをいろいろ書きます AtCoder A緑H水

Ideal Sheetをやっと解きました（偉い）

C - Ideal Sheet は、面倒な重実装の問題だと自分の中で知られています。コンテスト当時はABDの3完ということで、実装が思いつかなくて解けませんでした。やってみたら、意外といけました（良かった）。ということで、実装方針とそれに至った経緯を書いていきます。

問題の理解

シートAとシートBがあって、これを重ねて理想的なシートX（Ideal Sheet）と一致するかを判定する問題です。「#」は黒を表していて、シートを重ねたときにAまたはBのそのマスが黒なら、重ねた後は黒と判定されます。AとBはXからはみ出しても良くて、しかしAとBのすべての黒のマスはXの中に収まっていないといけないです。シートは上下左右の平行移動だけで、回転させたり裏返したりはできないです。

実装方針と考察の流れ

制約が小さく、AとBの重ね方を全探索できそうです。とりあえず図形の基準を決めたくて、今回は左上を固定しました。その中のループでAを探索して、Xと一致しているかを判定すれば良さそうです。例えば、Aの探索は以下の図のようにすることができます。



また、AとBのすべての黒いマスがXの中に含まれていないといけないらしいので、out_of_range(int i, int j)関数で判定しながら、領域外かつ黒のマスがあったら、その時点でその重ね方は条件を満たしていないと分かります。


計算量は、 1 \le N \le 10 として O(N^6) くらいだと思います。-10から10までの20回のループが4回あるので、実際には16倍くらいになって1600万回の計算とかで終わりそうです。ということでこの問題を解くことができました。実装は面倒な部分もありますが、適宜関数にしたり処理を分けたりしてバグらせないようにしていきたいですね。


提出URL：Submission #60884616 - Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307)

いかがでしたか

自分もコンテスト中に、重実装を10分とかで書けるようにしていきたいです。終わり。


「2048」をモンテカルロ法でプレイする

2048というスマホゲームを、UCT (Upper Confidence bound 1 applied to Trees) を使ったモンテカルロ法でプレイしました。人力でやっても面白いんですが、ヒューリスティックのパワーを適用したらどんな感じになるのか気になってやりました。かなり似ている例題として、AHC015の盤面を傾けてキャンディーをまとめる回があります。自分はそれを復習していたので、今回のアルゴリズムもそれで行けるのではないかと思いました。人力のスコアは26884点で、モンテカルロ法によるスコアは71712点になりました。




2048の紹介

2048は、盤面をスライドすると数字全体がその方向に動いて、それぞれ同じ数同士が足されて、どんどん数が大きくなっていくゲームです。ターンごとに新しい数字が盤面に増えていきます。



（人力プレイではこれくらいが限界だった）


これ以上スライドさせることができなくなったらゲームオーバーです。スコアは、新しい数 X を作ったら、 X が今のスコアに足されていきます。最初のスコアは 0 です。

モンテカルロ法とは

モンテカルロ法は、乱数を使って近似値を得るようなアルゴリズムの総称で、円周率を計算したりできます。また、ゲーム木探索にも使うことができます。

モンテカルロ木探索との関連について

モンテカルロ木探索 (MCTS) は、モンテカルロ法をゲーム木探索に応用したものですが、今回は一般にMCTSと言われているようなものとは少し違ったものを使っています。厳密にはMCTSなのかよく分からないですが、あえて言うなら「UCTを使ったモンテカルロ法」くらいの方が、伝わりやすそうな印象があります。

UCTとは

UCT (Upper Confidence bound 1 applied to Trees, いろいろな訳がありそう) とは、UCB1 (Upper Confidence Bound 1) を木上で使ったものです。UCB1の式は以下です。

参考：多腕バンディット問題におけるUCB方策を理解する · THINKING MEGANE


モンテカルロ木探索においてノードをプレイアウトするときに、この値が最大のノードを選択します。UCB1は、1項目の知識利用項と2項目の探索項でできています。知識利用というのは、そのノードの平均スコアのことで、そこまでのシミュレーションで得た知識（ノードの情報）をもとに、そのノードがどれだけ優れているかを取得します。探索というのは、あまり使われていないノードも使っていこうという意味で、 n がそのターンの全ノードの合計シミュレーション回数、 n_j がノード j のシミュレーション回数です。つまり、より使われていないノードほど、探索項の値が大きくなります。


要約すると、UCB1によってなるべくいいノードを選びつつ、あんまり使っていない方も見ていこう、その知識利用と探索のバランスを上手く取ろうみたいなニュアンスになります。


あとは、普通にモンテカルロ木探索のノードの展開を1層だけにして、原始モンテカルロをゲーム木上でやって終わりです。これで分かった人は、実際にやってみたり自分で考えても面白いかもしれないです。ここからは、コードの紹介になります。

実際のコードの説明


GitHub：GitHub - tombo314/MonteCarlo_2048


実装は結構気合なので、手法が同じであれば書き方は色々ありそうです。

UCB1

探索項の前に係数 c = 70000 を掛けて使いました。

double get_ucb1(int score, int trial_num, int trial_num_all){
    const double c = 70000;
    return (double)score/trial_num + c*sqrt(2*log(trial_num_all)/trial_num);
}


貪欲法

モンテカルロシミュレーションでは、次に来る数字を重み付きでランダムに予測（2が75%、4が25%、自分で簡単に検証）して、座標は空きマスから完全にランダムに予測して、スライドする方向は貪欲法に従って盤面を操作しました。


貪欲法は、下に大きい数字を集めるようにしました。分岐の優先度は高い方から順に、以下のようにしました。


1. 盤面を下にスライドしたときに、1個以上の数が合成されるならば下にスライドする
2. 盤面を左右にスライドしたときに、1個以上の数が合成されるならば、左右はどちらでも合成可能なので、ランダムに選んでスライドする
3. 盤面を下にスライドしたときに、1個以上の空きマスを詰めるならばスライドする
4. 盤面を左右にスライドしたときに、1個以上の空きマスを詰めるならば、その方向にスライドする（左右どちらも可能ならば、ランダムに選ぶ）
5. 上にスライドする

仕様について


turn：今のターン数
dir：その方向にスライドする
score：スライド後のスコア
スライド後のグリッドを表示


というようにしました。入力の与え方は、まず右に動いて、右端まで来たらその下の行の左からスタートするindex (1-indexed) を idx 、数字を num として


idx \; num


の形式で与えるようにしました。

モンテカルロ法を使った最終スコア




モンテカルロ法の自作AIに聞きながら、6～8時間くらい手動でスマホを操作します。すると、こうなります（長かった）。4096までは作ることができて、71712点ということで、人力の26884点に比べてとても良くなりました。かなりパワーのある手法だと思いました。AHCやコドゲでも使っていきたいです。こういうゲームAIを作るのは面白いので、皆さんもよかったらやってみてください。

参考にした記事

thunderさんありがとうございます。

AHC典型解法シリーズ第1弾「モンテカルロ法」 #AtCoder - Qiita

余談

将棋・オセロ・チェスに強いAlphaZeroは、MCTSにニューラルネットワークを組み合わせているらしいです。強そうですね。AHCやコドゲでも、この手法は有効そうなので、いろいろとやっていきたい感はあります。C++でNNのクラスを作るのありかもしれない。簡単なものなら作って使えそうだし。終わり。



AHC039（短期）の大まかな考察過程　1794パフォ

短期コンのAHC039に参加して、143位で1794パフォを取ることができました。スコアは332008です。今回は、そのざっくりとした考察過程をたどっていこうと思います。

問題を見る

AHC039：A - Purse Seine Fishing


イワシを取らないようにしながら、サバを集めます。これは自分のseed=0の画像です。

赤がサバ （1点）で、青がイワシ（-1点）です。多角形で囲んだ網の中の魚をすべて捕まえるということで、複雑な図形にすると難しそうだなーと思いました。では、考察に移ります。

考察1：焼きなまし

まず、問題を見ると焼きなましをしたくなってきます。文脈依存ではなく最後の形が良ければいいので、万能な焼きなましを選択します。これは実際に正しそうで、上位の方でも、より複雑ではあるものの、焼きなましが多かった気がしました。


複雑な図形は混乱しそうなので、長方形で考えます。近傍は縦横に伸ばしたり縮めたりでよさそうですね。斜めに角を動かす近傍は、あまり効果がないような感じでした。


移動距離も考察できそうです。短いのと長いのがあると、多様性があってうれしそうですね。ということで、2べきのリストを作って、そこからランダムに選ぶようにしました。[100, 200, 400, ..., 51200] という感じにしました。


動かしてみると、それなりによくなりました。ただ、適当な長方形をいきなり高温で焼くよりは、ある程度整えてからの方がいいなーとなりました。ということで、最初の100msは山登りで縦横にランダムに動かして、そこから焼きなましに移りました。


評価関数はルールベースです。

考察2：長方形を2個繋げる

できればデコボコな感じにして柔軟な焼きなましをしたいんですが、時間が4時間しかないしバグるとやばそうなので、いったん焼きなましはここまでにして、最後にちょっとだけ全探索をして長方形を1個追加して2個（焼きなまし＋全探索）にしようと思います。これだと、長方形1個だけよりも自明に良くなりそうです。できれば3個くらい加えたいですが、ちょっと時間がないです（そんな）


焼いた後の長方形の、上下左右のどこかに一番良くなるように長方形を入れることを考えます。探索は10000単位で動かすと、計算量が軽くなりそうです。（もうちょっと細かくても良かったかも）


これでだいたい完成しました。あとは焼きなましのスコア関数のハイパラをいじったり、温度を変えたりしながら人力チューニングして終わりです。ただしチューニングは誤差みたいなもので、方針が大事なので、これは最後で良くて、特に短期ではギリギリまで方針を工夫していきたいですね。


提出：Submission #59660116 - THIRD PROGRAMMING CONTEST 2024（AtCoder Heuristic Contest 039）

まとめ


1. 問題を見て、焼きなましをしたくなる
2. 短期なので、バグらないように近傍設計はシンプルにする
3. 山登りを最初に入れて改善する
4. 全探索で長方形を1個追加して、長方形2個（焼きなまし＋全探索）の構成にする

リソースをもっと使えるとよかったですね。今回は初の青パフォでうれしかったです。終わり。


ABC374G (diff 2608) 公式解説の再解釈

ABC374Gの公式解説を自分なりに解釈したものです。憶測が含まれているので、注意してください。公式解説の方が分かりやすい人もいると思うので、先にこちらをどうぞ。

公式解説：Editorial - KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374）


必要な知識（解説を省略します）

・強連結成分分解
・最大流
・二部グラフの最大マッチング


強連結成分分解：強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語

ACLのSCCのドキュメント (C++)：https://atcoder.github.io/ac-library/production/document_ja/scc.html


最大流：うさぎでもわかる離散数学（グラフ理論） 第15羽 最大フロー・最小カットの求め方 | 工業大学生ももやまのうさぎ塾

ACLのMaxFlowのドキュメント (C++)：https://atcoder.github.io/ac-library/production/document_ja/maxflow.html


最大流から二部グラフの最大マッチングへの応用は、鉄則演習Aの69が分かりやすいと思います。E8さんの解説コードを貼っておきます。


二部グラフの最大マッチング：A69 - Bipartite Matching

C++のACコード：kyopro-tessoku/codes/cpp/chap09/answer_A69.cpp at main · E869120/kyopro-tessoku · GitHub

PythonのACコード：kyopro-tessoku/codes/python/chap09/answer_A69.py at main · E869120/kyopro-tessoku · GitHub


必要に応じて検索したりして、知識を補充してください。

問題文の理解と、ざっくりとした考察

では問題を読んでみてください。

ABC374G：G - Only One Product Name


diffは2608で橙色なのでけっこう高めなんですが、緑コーダーの自分でも意外と2日くらいで理解できたので、他の人も結構いけると思います（ほんとか？）


入力例の画像


全部の文字列を連続部分列に含み、かつそれ以外の文字列を連続部分列に含まないような文字列の集合であって、最小であるような集合の大きさを求めよ、という問題ですね。自分は最初これを見て、有向グラフとトポロジカルソートを思いつきました。しかし、閉路があったり、そもそも文字列を全部含むような最小の文字列集合をどうやって求めるのか、まだ全然見当がついていなかったです。


少しだけ考えて、すぐに解説を開きました（早い）。ということで、公式解説の再解釈に移ります。ここで考えたい人は一回閉じてください。

公式解説の再解釈

いったん方針を書いておきます。

1. 商品に対応した有向グラフを作る。

2. 強連結成分分解をして、各成分を文字列に対応させる。

3. 分解後のグラフについて、最小パス被覆を求める。このときパスが文字列に対応するので、パスの本数が答えになる。


問題文を見ていると、なんとなく有向グラフに見えてきます。 1 \le i \le N について文字列 S_i を1つの頂点と見ると、求めるそれぞれの文字列は、そのまま S_i であるかもしくは複数の S_i を連結させたものだと分かります。これによって、まずは 1 \le i \le N \, (i \neq j) について、 S_i の2文字目と S_j の1文字目が等しいかを愚直に見て連結させて、有向グラフ G を作ります。

ここで閉路がありますが、これは巡回して同じ文字に戻ってくるような1つの文字列と見ることができます。また、巡回しない部分もそれぞれ1つの文字列と見ることができ、これは G を強連結成分分解をしたときに、各成分がそれぞれ1つの文字列、または複数の文字列を連結させたものに対応する、と考えることができそうです。

求めたいものは、全体を包括する文字列の集合なので、グラフで言うと「全部の頂点を通るようなパスの集合であって、含まれるパスの本数が最小のもの」ということになりますね。先ほど強連結成分分解したグラフを G' とすると、これは G' における最小パス被覆という概念と完全に一致しています。（自分は知らなかったです）


最小パス被覆とは、すべての頂点を覆うようなパスの集合であって、集合の大きさが最小のものです。パス（道）については、うさぎ塾がおすすめです。

うさぎでもわかる離散数学（グラフ理論） 第8羽 グラフの基礎2 歩道・小道・道・回路・閉路とは | 工業大学生ももやまのうさぎ塾


ここまでを振り返ると、まずそれぞれの文字列 S_i を連結してグラフ G を作り、それを強連結成分分解して G' を作ります。 G' 上の1つの成分を1つの文字列、または複数の文字列の連結に対応させると、答えは G' における最小パス被覆になると分かります。


ここで最小パス被覆についてさらに調べてみると、どうやら最大流に帰着させられるらしいです。

最大反鎖や最小パス被覆を堅実に解く - noshi91のメモ


ここからは自分の解釈なので正当性はよく分からないですが、以下のように理解しました。



今、SCC分解されて作られた G' の各成分を1つの頂点、1つの結合された文字列とします。このとき、自己ループの辺を張らないようにしながら、 G' 上で頂点 i から頂点 j \; (i \neq j) に到達可能であるならば、MaxFlowのオブジェクト mf に add\_edge(i, j, 1) するとします。こうして作られた mf のグラフ G_{mf} 上で最大流を得ると、そのフローに含まれる頂点はすべて独立でない（それ以外の1つ以上の頂点と連結である）と言えます。このとき自己ループはないことに注意します。最大マッチングになっているので、そのような独立でない頂点の数が最大化されていると思います。


そして、Dilworthの定理から、最大独立集合の大きさは最小パス被覆の大きさと等しいので、 G_{mf} の頂点数を N_{mf} 、最大流の値を flow_{mf} とすると、残った独立な頂点の数であり求める ans は


ans = N_{mf} - flow_{mf}


となることが分かります。


Dilworthの定理：競プロで使う Dilworth の定理 - miscalc のブログ


計算量は O(N^3) らしいですが、自分のコードがそうなっているのかよく分かっていません。39msで実行できたので、十分速そうではあります。


ACコード (C++)


以下は自分のACコードです。

#include <bits/stdc++.h>
#include <atcoder/maxflow>
#include <atcoder/scc>
using namespace std;

// G, N, start=0
// 0-indexed
struct BFS {
    
    int start;
    const int inf = 1e9;
    queue<int> q;
    vector<int> dist;
    vector<vector<int>> G;

    BFS(vector<vector<int>> G_, int N, int start_=0){
        G = G_;
        start = start_;
        dist.resize(N, inf);
        dist[start] = 0;
        q.push(start);
    }

    void run(){
        while (q.size()){
            int n = q.front();
            q.pop();
            for (auto v: G[n]){
                if (dist[v]!=inf) continue;
                dist[v] = dist[n]+1;
                q.push(v);
            }
        }
    }

    vector<int> get_dist(){
        return dist;
    }
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    vector<string> S(N);
    for (int i=0; i<N; i++){
        cin >> S[i];
    }

    vector<vector<int>> G(N);
    atcoder::scc_graph scc(N);

    // 文字列をつなげてグラフを作る
    // scc分解のグラフも構築する
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            if (i==j){
                continue;
            }
            if (S[i][1]==S[j][0]){
                scc.add_edge(i, j);
                G[i].emplace_back(j);
            }
        }
    }
    
    // scc分解をする
    vector<vector<int>> comps = scc.scc();
    int M = comps.size();

    // グラフG上で、お互いに到達可能な頂点のペアを得る
    const int inf = 1e9;
    atcoder::mf_graph<int> mf(2*M+2);
    vector reachable_g1(N, vector(N, false));

    for (int i=0; i<N; i++){
        BFS bfs{G, N, i};
        bfs.run();
        vector<int> dist = bfs.get_dist();

        for (int j=0; j<N; j++){
            if (j==i){
                continue;
            }
            if (dist[j]!=inf){
                reachable_g1[i][j] = true;
            }
        }
    }

    // グラフG'上で、お互いに到達可能な頂点のペアを得る
    vector reachable_g2(N, vector(N, false));
    for (int i=0; i<M; i++){
        for (int j=0; j<M; j++){
            if (i==j){
                continue;
            }
            for (auto x: comps[i]){
                for (auto y: comps[j]){
                    if (reachable_g1[x][y]){
                        reachable_g2[i][j] = true;
                    }
                }
            }
        }
    }

    // どこから始まってどこで終わってもいいので、
    // 始点と終点をすべての頂点に設定する
    for (int i=0; i<M; i++){
        mf.add_edge(2*M, i, 1);
        mf.add_edge(i+M, 2*M+1, 1);
    }

    // 到達可能ならば、流量1の辺を張る
    for (int i=0; i<M; i++){
        for (int j=0; j<M; j++){
            if (i==j){
                continue;
            }
            if (reachable_g2[i][j]){
                mf.add_edge(i, j+M, 1);
            }
        }
    }

    // 始点から終点までの最大流を得る
    int ans = mf.flow(2*M, 2*M+1);

    cout << M-ans << endl;
}


提出：Submission #59316315 - KEYENCE Programming Contest 2024（AtCoder Beginner Contest 374）

解説ACした感想

正直理解が怪しいところがあるんですが、橙diffの問題を一応通すことができて、内容もそこそこ分かったつもりではあるので、また最小パス被覆や最大二部マッチングを使う問題を見つけたら生かせるようにしたいです。



メインページ

〇競技プログラミング

アルゴリズム

・マージソートを、書きます。 - tomboのブログ

・茶色コーダーが書く！例題を通して畳み込みを感覚的に理解する - tomboのブログ

・mod の演算・フェルマーの小定理・確率（期待値）mod 998・期待値の考え方と例題 - tomboのブログ

・3種類の平方分割をします - tomboのブログ

・PuLPの使い方 ナップサックDPも解けます - tomboのブログ

・遅延セグ木の使い方 Range Affine Range Sum - tomboのブログ

・ダブリングで遷移を加速する - tomboのブログ

・ABC374G (diff 2608) 公式解説の再解釈 - tomboのブログ

・Ideal Sheetをやっと解きました（偉い） - tomboのブログ

ヒューリスティック

・初心者から初心者に向けた焼きなましのすすめ - tomboのブログ

・AHC039（短期）の大まかな考察過程 1794パフォ - tomboのブログ

・「2048」をモンテカルロ法でプレイする - tomboのブログ


その他

・AHCのローカルテスタの使い方 - tomboのブログ


〇将棋ライク

・将棋ライクLv.20クリアしました！ - tomboのブログ



ダブリングで遷移を加速する

ダブリングをします。例題にはABC367Eを使います。

ダブリングとは

ダブリングとは、遷移を2のべき乗個ごとにまとめることによって、遷移を高速に行うアルゴリズムです。よくDPの形で書かれたりするので、本記事でもそのような書き方をします。

本質部分のコード

C++で書きます。

// dp[i][j] := 場所jから2^i回遷移したあとの場所
dp[i][j] = dp[i-1][dp[i-1][j]]


ここがダブリングの一番大事なところです。これは、「今いる場所 n0 から x 回遷移した後にいる場所 n1」から、「さらに x 回遷移した後にいる場所 n2」を求めるということで、つまり 2x 回遷移しています。遷移後には 2x 回ですが、これをもう一回やると 4x, 8x, 16x, 32x, ...... となって、指数関数的に遷移回数が増えていきます。 K 回遷移後の場所は、 O(logK) 回遷移することで求めることができます。

例題

問題：E - Permute K times
提出：Submission #56854848 - AtCoder Beginner Contest 367


ダブリングをそのまま出題したような問題です。遷移する先が分かっていて、同じ集合に返ってくるような感じなので、ダブリングができます。集合も高々 10^5 程度の大きさなので十分小さいです。

// indexとvalueはどちらも0-indexed
struct Doubling {

    vector<vector<int>> dp;
    const int M = 60;

    Doubling(vector<int> A){
        int N = A.size();
        dp.resize(M+1);
        for (int i=0; i<=M; i++){
            dp[i].resize(N);
        }
        for (int i=0; i<N; i++){
            dp[0][i] = A[i];
        }
        for (int i=1; i<=M; i++){
            for (int j=0; j<N; j++){
                dp[i][j] = dp[i-1][dp[i-1][j]];
            }
        }
    }

    ll get(int now, ll move_num){
        ll n = now;
        for (int i=M; i>=0; i--){
            if ((move_num/(1LL<<i))%2!=0) n = dp[i][n];
        }
        return n;
    }
};


まず、遷移に使うテーブルを受け取って、初期値を設定します。そこから2回分まとめて遷移すると、それまでの遷移回数が2倍になるので、指数関数的な増え方になってデカ遷移が間に合います。


最後に、 K 回遷移したあとの場所を得ます。今、 2^i 回ごとに遷移しているので、 K を2進数で見たときに、bitが立っているところの遷移だけを採用したいです。 K をシフトしていって、1だったら現在の場所からそこに飛ぶ、みたいなことを書けばよいです。この問題では、 N 要素に対して O(logK) 時間かかるので、全体の計算量は O(NlogK) となり間に合います。


M=60 なのは、 10^{18} < 2^{60} ということです。

まとめ

指数関数ってすごいですよね（？）

遅延セグ木の使い方　Range Affine Range Sum

遅延セグメント木（Lazy Segment Tree）の使い方を解説します。

セグメント木とは

セグメント木（以下、セグ木）とは、二分木を作り、各ノード（頂点）に区間の情報を与えることで、区間クエリに O(logN) で答えることができるデータ構造です。セグ木にはモノイドが乗ります。モノイドとは、以下の性質を満たす「集合Sと二項演算Fの組」です。


1. Fについて閉じている
Sの元と元でFをしたとき、その返り値がSの元である。


2. 結合則を満たす
例えば、Sの元s1、s2、s3について、F(F(s1, s2), s3) == F(s1, F(s2, s3))が成り立つ。
つまり、順番はそのままにしてどこから演算を行ってもよい。


3. 単位元がある
とあるSの元eが存在して、任意のSの元sに対してF(s, e)==sが成り立つ。
つまり、何回計算しても答えに影響を与えないような要素がある。
例えば、
足し算：0を足す
掛け算：1を掛ける
最小公倍数：1との最小公倍数を取る
最大公約数：0との最大公約数を取る
最小値の更新：取り得る一番大きい値よりも大きい値で更新する
最大値の更新：取り得る一番小さい値よりも小さい値で更新する
などです。


ちなみに、モノイドの集合Sについて、全部の元sに逆元s'がある（F(s, s') == e、eは単位元）とき、群と言います。


セグ木は、ノードが持つ要素の個数が2のべき乗になっています。区間クエリが欲しかったら、2のべき乗個ごとにまとまったものを二項演算Fでまとめるだけなので、 O(logN) でこれを達成することができます。


普通のセグ木では一点更新・区間加算など、取得クエリのみ区間から得ることができます。もしくはimos法のようにして、区間加算・一点取得などもできますが、加算と取得の両方を区間に対して行うことはできません。それに対して、遅延セグメント木ではそれが可能です。

遅延セグメント木とは

遅延セグメント木（以下、遅延セグ木）とは、2のべき乗個ごとにまとめられたものをData層と呼ぶならば、さらにLazy層を追加することで、区間加算や区間更新などを O(logN) で行うデータ構造です。


区間への加算を愚直にやっていたら、間に合いません。そこで、Lazyにこれから伝播する値を持たせておきます。セグ木の取得と同じように、加算のときにも、当てはまる区間のノードに加算分を足します。これを取得クエリのときにcomposition（合成写像）で合成してから、mapping（写像）で要素に適用することで、やはり O(logN) で区間クエリに答えることができます。



参考：Pythonで遅延セグメントツリーの問題を解けるようにする！ #AtCoder - Qiita


遅延セグ木を使ってみる

言語はC++、ライブラリはAtCoder Libraryを使います。ALPC（AtCoder Library Practice Contest）のK問題を解きます。


問題：K - Range Affine Range Sum


これは、区間の各要素にアフィン変換（a倍してb足す）をして、区間の和を取得するというクエリに答える問題です。遅延セグ木では、二項演算や単位元はいいとして、mappingとcompositionの設計が重要になってきます。また、単位元の写像バージョンである、恒等写像も要求されます。これは、何回適用しても要素が変わらない写像ということで、単位元と似ています。


では、実際のコードを見てください。

#include <atcoder/lazysegtree>
#include <atcoder/modint>

using mint = atcoder::modint998244353;

struct S {
    mint sum;
    ll sz;
};

struct F {
    mint b;
    mint c;
};

vector<S> a(N);
rep(i, 0, N){
    ll tmp;
    cin >> tmp;
    a[i] = {tmp, 1};
};

auto op = [](S s1, S s2){
    return S{s1.sum+s2.sum, s1.sz+s2.sz};
};
auto ids = []{
    return S{0, 1};
};
auto mapping = [](F f, S s){
    return S{f.b*s.sum+f.c*s.sz, s.sz};
};
/*
b1(b2(ai)+c2)+c1
= (b1b2)ai+(b1c2+c1)
*/
auto composition = [](F f1, F f2){
    return F{f1.b*f2.b, f1.b*f2.c+f1.c};
};
auto idf = []{
    return F{1, 0};
};

atcoder::lazy_segtree<S, op, ids, F, mapping, composition, idf> seg(a);


一部だけ切り抜きました。これを作ることができれば、あとはseg.apply(l, r, x)で[l, r)にxを作用させ、seg.prod(l, r)で区間クエリを取得して終わりです。この構築が難しかったりして、特にmappingとcompositionを見てください。また、元Sと作用素Fはどのようになっているかにも注目してください。ここで、SはDataであり、FはLazyです。


まず、遅延セグ木には8個の要素が必要です。
1. 元の型S
2. 二項演算op
3. 単位元ids（identity S）
4. 作用素の型F
5. 作用素と元から、元への写像mapping
6. 合成写像composition
7. 恒等写像idf（identity F）
8. 遅延セグ木のサイズ（単位元で初期化される）
（または、型Sの初期化配列）


1. 元の型S
区間加算をするとき、サイズlが分かると、それらすべてにxを足すので、全体の合計にはl倍のx足せばよいことが分かります。これがうれしいので、Sは構造体として、区間和と区間のサイズを持たせておきます。


2. 二項演算op
二つの型Sの元s1とs2が与えられたとき、これらを取得クエリとしてマージする際の計算です。今、区間和と区間のサイズを持っているので、それぞれ足せばよいです。


3. 単位元ids
元なので、型はSです。区間和は0を足しても変わらず、元としてサイズは1であるので、S{0, 1}が単位元となります。


4. 作用素の型F
b倍してc足すので、情報としてはbとcが欲しいです。これを構造体で持ちます。


5. 作用素と元から、元への写像mapping
難しいポイント1です。SにFを適用することを考えます。元SにF.b倍してF.cを足します。ここで、Sはすでにその区間全体が足されているので、そのS.sumを単にF.b倍すれば、全要素にF.b倍したことになります。また、S.szで区間のサイズが分かるので、S.sz倍してF.c足せば、全要素の分F.c足したことになり、これをS.sumに足せばよいです。サイズはLazyを適用しても変わらないので、そのままS.szを渡します。


6. 合成写像composition
難しいポイント2です。F f1とF f2について、それらの合成写像fを考えます。元sに対して、f = f1(f2(s))として合成します。これを展開すると、画像のようになり、最終的にf.b = f1.b×f2.b倍して、f.c = f1.b×f2.c+f1.cを足すことと同じとなり、それらをfとして返します。


7. 恒等写像idf
何回適用しても元が変わらない作用素Fなので、b = 1、c = 0とすると、1倍して0足すとなり、うまくいきます。


8. 遅延セグ木のサイズまたは、初期化配列
問題文で与えられている通りです。


これで遅延セグ木を完成させることができました。あとはクエリに素直に答えていけばよいです。

vector<S> ans;

rep(_, 0, Q){
    ll t;
    cin >> t;

    if (t==0){
        ll l, r, b, c;
        cin >> l >> r >> b >> c;
        seg.apply(l, r, F{b, c});
    } else {
        ll l, r;
        cin >> l >> r;
        ans.emplace_back(seg.prod(l, r));
    }
}


提出：Submission #56201586 - AtCoder Library Practice Contest


これでこの問題は終わりです。しかし、何かに気づいた人はいませんか？（？）なんと、区間更新という演算には恒等写像が存在しません。何かの値に更新すると、元の値が変わってしまうため、影響を与えないような区間更新というものは存在しません。そのようなとき、恒等写像idfはどのように扱えばよいでしょうか。また、mappingやcompositionは、その恒等写像とどのように関わるでしょうか。

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.


答え：擬似的な恒等写像として、取り得ない値にしておく。mappingとcompositionは、恒等写像と一致しているかどうかで場合分けをする。


以下はRange Update Range Minimumのコードの例です。

auto op = [](ll a, ll b){
    return min(a, b);
};
auto ids = []{
    return inf;
};
auto mapping = [](ll f, ll s){
    if (f==-1){
        return s;
    } else {
        return f;
    }
};
auto composition = [](ll f1, ll f2){
    if (f1==-1){
        return f2;
    } else {
        return f1;
    }
};
auto idf = []{
    return -1LL;
};


Range Minimumなので、opは最小値、idsはinfとなっています。問題は作用素の方で、まず、取り得る値の範囲を[1, 10^9]などと仮定して、恒等写像は-1にしておきます。すると、mappingやcompositionに登場する作用素fは、-1のとき、何もしないとして扱うことができます。これを恒等写像とします。すると、あとは普通の遅延セグ木と同じように使うことができます。


compositionはcomposition(ll f1, ll f2)のとき、f2→f1の順に適用するので、f1が-1かどうかで場合分けすることに注意してください。

まとめ

遅延セグ木には、和や最大値などの他に、サイズや個数など様々なものを持たせることができ、いろいろと便利なので使ってみてください。