結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー IKyopro
提出日時 2019-09-06 23:30:28
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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