Quiz
https://yukicoder.me/problems/no/875
AC code
https://yukicoder.me/submissions/442780
補足
- クエリに答えるときに、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; }
![プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～](https://m.media-amazon.com/images/I/41bHxtpurqL._SL160_.jpg "プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～")
