結果

問題 No.875 Range Mindex Query
ユーザー RubikunRubikun
提出日時 2019-11-27 03:13:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 287 ms / 2,000 ms
コード長 1,832 bytes
コンパイル時間 1,521 ms
コンパイル使用メモリ 170,876 KB
実行使用メモリ 6,016 KB
最終ジャッジ日時 2024-04-24 20:11:16
合計ジャッジ時間 5,236 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 193 ms
5,888 KB
testcase_12 AC 160 ms
5,376 KB
testcase_13 AC 137 ms
6,016 KB
testcase_14 AC 133 ms
5,888 KB
testcase_15 AC 182 ms
6,016 KB
testcase_16 AC 259 ms
6,016 KB
testcase_17 AC 287 ms
6,016 KB
testcase_18 AC 251 ms
6,016 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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