結果

問題 No.875 Range Mindex Query
ユーザー IKyoproIKyopro
提出日時 2019-09-06 23:30:28
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 258 ms / 2,000 ms
コード長 1,734 bytes
コンパイル時間 869 ms
コンパイル使用メモリ 67,692 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-24 21:25:56
合計ジャッジ時間 3,528 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 3 ms
6,944 KB
testcase_11 AC 183 ms
6,944 KB
testcase_12 AC 153 ms
6,944 KB
testcase_13 AC 129 ms
6,940 KB
testcase_14 AC 129 ms
6,940 KB
testcase_15 AC 175 ms
6,944 KB
testcase_16 AC 240 ms
6,940 KB
testcase_17 AC 258 ms
6,940 KB
testcase_18 AC 246 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <climits>
#include <functional>
using namespace std;

template<typename Monoid>
class SegmentTree{
private:
    using F = function<Monoid(Monoid,Monoid)>;
    int sz;
    vector<Monoid> seg;
    const F op;//演算
    const Monoid e;//単位元
public:
    SegmentTree(int n,const F op,const Monoid &e):op(op),e(e){
        sz = 1;
        while(sz<n) sz <<= 1;
        seg.assign(2*sz,e);
    }
    //代入
    void set(int k, const Monoid &x){
        seg[k+sz] = x;
    }
    //前計算
    void build(){
        for(int i=sz-1;i>0;i--){
            seg[i] = op(seg[2*i],seg[2*i+1]);
        }
    }
    void update(int k,const Monoid &x){
        k += sz;
        seg[k] = x;
        while(k>>=1){
            seg[k] = op(seg[2*k],seg[2*k+1]);
        }
    }
    Monoid query(int l,int r){
        Monoid L = e,R = e;
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1) L = op(L,seg[l++]);
            if(r&1) R = op(seg[--r],R);
        }
        return op(L,R);
    }
    Monoid operator[](const int &k)const{
        return seg[k+sz];
    }
};

int main(){
    int N,Q;
    cin >> N >> Q;
    SegmentTree<int> 
    seg(N,[](int a,int b){return min(a,b);},1e9);
    vector<int> p(N);
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
        a--;
        p[a] = i;
        seg.set(i,a);
    }
    seg.build();
    for(int q=0;q<Q;q++){
        int c,l,r;
        cin >> c >> l >> r;
        if(c==1){
            l--; r--;
            swap(p[seg[l]],p[seg[r]]);
            int a = seg[l];
            seg.update(l,seg[r]);
            seg.update(r,a);
        }else{
            l--; r--;
            cout << p[seg.query(l,r+1)]+1 << endl;
        }
    }
}
0