Quiz

AC code

補足

クエリに答えるときに、min値を持つ場所のindexを返す必要がある
だから min + index = mindex というタイトルなのだろう
遅延なしSegTreeは書いたことがあったのでそれをコピーしてきて、値だけ持っていた場所を(値, index)のペアに書き換えた
思った以上に書き換えがすぐ終わった。やはり自作ライブラリは手を入れやすい

mindex segment tree

// range min, and index (range Mindex)
struct SegmentTree{
    vector<PII> A;
    ll N; // node num
 
    // 初期化
    SegmentTree(ll size){
        N = _powerOfTwo(size); //2べき
        auto initial_value = MP((1LL<<31)-1LL, -1);
        A.resize(N * 2, initial_value); // 木なので2倍必要
    }

    void update(ll i, ll x){
        int index = N + i - 1; // 葉のインデックス
        A[index].first = x;
        A[index].second = i;
        // 親にも反映
        while(index > 0){
            PII min0 = A[index];
            PII min1;
            if(index%2==0){
                min1 = A[index-1];
            }else{
                min1 = A[index+1];
            }

            ll parent = (index-1) / 2;
            A[parent] = min(min0, min1);
            index = parent;
        }
    }

    bool is_power_of_two(ll v){
        return !(v & (v-1));
    }
 
    // 引数以上の2のべき乗 5=>8
    ll _powerOfTwo(int n){
        ll ret = 1;
        while(ret < n){
            ret *= 2;
        }
        return ret;
    }
 
    // 区間[a,b)の総和。ノードk = [l,r) に着目している
    PII _rangeMin(int a, int b, int k, int l, int r){
        // 重ならない
        if(r <= a || b <= l){
            return MP(inf, -1);
        }
        // 内包する
        else if(a <= l && r <= b){
            return A[k];
        }
        // 重なる部分もある
        else{
            ll center = (l+r) / 2;
            // 左下の子
            auto min0 = _rangeMin(a, b, 2*k+1, l, center);
            // 右下の子
            auto min1 = _rangeMin(a, b, 2*k+2, center, r);
            return min(min0, min1);
        }
    }
 
    // [a, b) までのmin
    // 半開区間
    PII RangeMin(int a, int b){
        return _rangeMin(a, b, 0, 0, N);
    }
};

解答コード(抜粋)

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

    // input
    ll N,Q;cin>>N>>Q;
    VI A(N);
    rep(i,N)cin>>A[i];

    auto seg = SegmentTree(N);
    rep(i,N){
      seg.update(i, A[i]);
    }

    while(Q--){
      ll ty;cin>>ty;
      ll l,r;cin>>l>>r;
      l--;r--;
      if(ty==1){
        // swap
        ll a = seg.RangeMin(l, l+1).first;
        ll b = seg.RangeMin(r, r+1).first;
        seg.update(l, b);
        seg.update(r, a);
      }
      else{
        // print
        PII a = seg.RangeMin(l, r+1);
        p(a.second+1);
      }
    }
    
    return 0;
}