Submission #77281

ソースコード

#include<bits/stdc++.h>
using namespace std;
struct segtree{
    int sz;
    vector<int>seg;
    segtree(int n){
        /*
        sz = n をセグ木にするとき、空白を含めた最終ノードの数
        親は1/2ずつ増えていく。また、szは２^nである。
        よって、ノードの総数はsz*2-1で表せる。（２進数の考え方）
        */
        sz = 1;
        while(sz < n)sz <<= 1;
        //sz を　ｎ以上かつ最小の2^mにする。（ｍは整数,不定）
        seg.assign((sz*2)-1,INT_MAX);
        //ノードのすべてを解に影響しない値で埋める。（今回はminなので、INT_MAX）
    }
    void update(int a,int b){
        /*
        子ノードを更新する。
        その後、親ノードを０までたどり、更新。
        O(log n)
        */
        a += sz-1;
        //子ノードの位置をaにする。
        seg[a] = b;
        //子ノードのa番目をbにする。
        while(a > 0){
            a =(a-1)>>1;
            //aを(a-1)/2する。つまり、親ノードの位置を指す。
            seg[a] = min(seg[(2*a)+1],seg[(2*a)+2]);
            //さっき選択したノードを条件に従って更新。
        }
    }
    int rmq(int a,int b,int k,int l,int r){
        /*
        a-bのとl-rが被っていないならば、解に影響しない値。
        完全にl-rがa-bの間に入っている場合はその値を返す。
        l-rがa-bに被っている場合は現在のノードの子ノード２つを参照する。
        aは探したい地点の開始点。
        bは探したい地点の終点。
        kは現在のノード。
        lは現在のノードの参照範囲の開始点。
        rは現在のノードの参照範囲の終点。
        */
        if(a >= r||l >= b)return INT_MAX;
        //被っていない判定(範囲の最初より参照範囲の終点が前にある||範囲の終点より参照範囲の始点が後ろにある)
        //"="がついているので、端の数は注意
        if(a <= l&&b >= r)return seg[k];
        //完全にかぶっている判定
        return min(rmq(a,b,(k*2)+1,l,(l+r)>>1),rmq(a,b,(k*2)+2,(l+r)>>1,r));
        //一部被っている判定。子ノード２つを参照し、条件にあった値を返す。
    }
    int rmq(int a,int b){
        /*
        ただのショートカット。
        */
        return rmq(a,b,0,0,sz);
    }
};
int main(){
    int n;cin>>n;
    segtree t(n);
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        t.update(i,a[i]);
    }
 
    while(1){
        string s;cin>>s;
        if(s=="exit")return 0;
        int x,y;cin>>x>>y;
        if(s=="min"){
            cout<<t.rmq(x,y+1)<<"\n";
        }
        if(s=="update"){
            t.update(x,y);
        }
    }
}

ステータス

項目	データ
問題	0459 - セグメントツリー練習
ユーザー名	ei2331
投稿日時	2023-11-20 16:49:37
言語	C++17
状態	Accepted
得点	10
ソースコード長	2943 Byte
最大実行時間	61 ms
最大メモリ使用量	2268 KB

セット

	セット	得点	Cases
1	ALL	10 / 10	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
Input01	AC	35 ms	600 KB	1
Input02	AC	21 ms	692 KB	1
Input03	AC	28 ms	540 KB	1
Input04	AC	20 ms	512 KB	1
Input05	AC	20 ms	612 KB	1
Input06	AC	30 ms	576 KB	1
Input07	AC	21 ms	416 KB	1
Input08	AC	25 ms	508 KB	1
Input09	AC	28 ms	592 KB	1
Input10	AC	61 ms	2268 KB	1