はまやんはまやんはまやん

hamayanhamayan's blog

Multiple Min Query [第七回 アルゴリズム実技検定 L]

競技プログラミング

https://atcoder.jp/contests/past202107-open/tasks/past202107_l

前提知識

解説

https://atcoder.jp/contests/past202107-open/submissions/24471772

解法を思いつくのも難しいが、ならし計算量（償却計算量）も意識する必要があり、そこも難しい。
セグメントツリーの知識が要求される。もし知らない場合はどこかで学習してくるか、AtCoder Libraryを活用するのもいいだろう。

何から考え始めるか

まず問題をパッと見て、単一要素更新と、区間最小値なのでセグメントツリーっぽさがある。
区間の中の最小値そのものではなく、最小値を持つ添え字を答えるというのが特徴となるが、
まずはセグメントツリーベースで考えていこう。

全て列挙するとあるが、1つ列挙することはできないだろうか。
これはセグメントツリーのノードを工夫することで実現ができる。
通常は要素のみを入れるが、{要素,添え字}というpairで入れることにする。
つまり{A[i],i}を入れるということになるのだが、これを入れてそのままmin関数で最小値を持ってきたとする。
こうすると、pairのmin比較では、firstが小さい方が採用され、firstが同じであればsecondの小さい方が採用される。
つまり、要素が最も小さく、かつ、その中でも添え字が最も小さいものが選ばれる。
こうすることで、セグメントツリーから得られる情報は要素が最も小さく、区間の中で最も左にある要素が得られることになる。

ここまで理解できていれば、実はこれ以降はそれほど難しくなくて、区間を小さくしながら要素を愚直に持ってくるだけでいい。

クエリ1

クエリ1は単純にセグメントツリーの更新処理を走らせればいい。
{Y, X}でX番目を更新する。

クエリ2

問題はこっち。
最初に区間全体でセグメントツリーから取ってきて、最小値をメモっておこう。
ここから区間の左端を狭めながら、最小値となる添え字を全列挙していく。

最初は[X,Y]の区間でセグメントツリーから持ってきて、{min, a}が得られたとする。
これは[X,Y]の区間の最左の要素となるので、次に見る区間はそれ以降でよいということになる。
よって、区間を[a+1,Y]のように更新して再度セグメントツリーから持ってくる。
同じ最小値のものが持ってこれたら再度答えとしてメモって、区間を狭くする。

これを繰り返していけば、要素が全列挙できることは分かるだろう。

間に合うのか？

とても素直な回答で、間に合うのか？という疑問が出てくるかもしれない。
今回は制約の「列挙すべき個数は2×105を超えない」というのが効いてくる。
この探索作業は必ず「列挙すべき個数+1」回の探索を行う（1回は失敗分）。
これをすべてのクエリについて足し合わせると、「列挙すべき個数の総和+Q」回となり、
多くても4×105回となるため、全体で考えると回数的には問題ないので間に合う。

このように計算回数にばらつきはあるのだけれど、全体で見るとある一定の回数に収まるというのを
ならし計算量、償却計算量で考えると表現する。
難しい考え方ではあるが、イメージをつかめば使いこなせるだろう。

int N, Q, A[201010];
SegTree<1<<18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) st.update(i, { A[i], i });

    rep(_, 0, Q) {
        int T, X, Y; cin >> T >> X >> Y;
        if (T == 1) {
            X--;
            st.update(X, { Y, X });
        }
        else {
            X--;
            int mi = st.get(X, Y).first;

            vector<int> ans;
            while (X < Y) {
                auto p = st.get(X, Y);
                if (p.first != mi) break;

                ans.push_back(p.second);
                X = p.second + 1;
            }
            
            int M = ans.size();
            printf("%d", M);
            rep(i, 0, M) printf(" %d", ans[i] + 1);
            printf("\n");
        }
    }
}