結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー Rubikun
提出日時 2019-11-27 03:13:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 283 ms / 2,000 ms
コード長 1,832 bytes
コンパイル時間 1,861 ms
コンパイル使用メモリ 174,620 KB
実行使用メモリ 6,144 KB
最終ジャッジ日時 2024-11-07 05:04:27
合計ジャッジ時間 5,876 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=1<<21,INF=1<<30;

template<typename T>
struct SegmentTree{
    using F=function<T(T,T)>;
    
    int n;
    vector<T> dat;
    F f;
    T ti;
    
    SegmentTree(int n_ ,F f ,T ti) :f(f),ti(ti){
        n=1;
        while(n<n_) n*=2;
        dat.assign(2*n-1,ti);
    }
    
    SegmentTree(int n_ ,vector<T> &v ,F f,T ti) :f(f),ti(ti){
        n=1;
        while(n<n_) n*=2;
        dat.assign(2*n-1,ti);
        
        for(int i=n-1;i-(n-1)<v.size();i++) dat[i]=v[i-(n-1)];
        
        for(int i=n-2;i>=0;i--) dat[i]=f(dat[i*2+1],dat[i*2+2]);
    }
    
    void update(int k,T x){
        k+=n-1;
        dat[k]=x;
        
        while(k){
            k=(k-1)/2;
            dat[k]=f(dat[k*2+1],dat[k*2+2]);
        }
    }
    
    T query_(int a,int b,int k,int l,int r){
        if(r<=a||b<=l) return ti;
        if(a<=l&&r<=b) return dat[k];
        else{
            T vl=query_(a,b,2*k+1,l,(l+r)/2);
            T vr=query_(a,b,2*k+2,(l+r)/2,r);
            return f(vl,vr);
        }
    }
    
    T query(int a,int b){
        return query_(a,b,0,0,n);
    }
    
    T get(int k){
        return dat[k+n-1];
    }
    
};

int main(){

    int N,Q;cin>>N>>Q;
    vector<pair<int,int>> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i].first;
        A[i].second=i+1;
    }
    SegmentTree<pair<int,int>> seg(N,A,[](pair<int,int> a,pair<int,int> b){return min(a,b);},{INF,0});
    
    while(Q){
        int c,x,y;cin>>c>>x>>y;
        x--;y--;
        if(c==1){
            auto l=seg.get(x),r=seg.get(y);
            seg.update(x,{r.first,x+1});
            seg.update(y,{l.first,y+1});
        }else cout<<seg.query(x,y+1).second<<endl;
        
        Q--;
    }
    
}
0