結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー otamay6
提出日時 2019-09-06 21:42:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 264 ms / 2,000 ms
コード長 1,784 bytes
コンパイル時間 1,797 ms
コンパイル使用メモリ 176,744 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-24 17:18:17
合計ジャッジ時間 4,362 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
template <typename T,typename E> //SegmentTree((要素数) int n_,(演算) F f,(更新) G g,(初期値) T d1)
struct SegmentTree{
  typedef function<T(T,T)> F;
  typedef function<T(T,E)> G;
  int n;
  F f;
  G g;
  T d1;
  E d0;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int n_,F f,G g,T d1,
	      vector<T> v=vector<T>()):
    f(f),g(g),d1(d1){
    init(n_);
    if(n_==(int)v.size()) build(n_,v);
  }
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,d1);
  }
  void build(int n_, vector<T> v){
    for(int i=0;i<n_;i++) dat[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--)
      dat[i]=f(dat[i*2+1],dat[i*2+2]);
  }
  void update(int k,E a){
    k+=n-1;
    dat[k]=g(dat[k],a);
    while(k>0){
      k=(k-1)/2;
      dat[k]=f(dat[k*2+1],dat[k*2+2]);
    }
  }
  inline T query(int a,int b){
    T vl=d1,vr=d1;
    for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,dat[(l++)-1]);
      if(r&1) vr=f(dat[(--r)-1],vr);
    }
    return f(vl,vr);
  }
  
};
int main(){
    int N,Q;cin>>N>>Q;
    SegmentTree<int,int> seg(N,[](int a,int b){return min(a,b);},[](int a,int b){return b;},1e9);
    vector<int> a(N),pos(N+1);
    REP(i, N){ 
        cin >> a[i];
        pos[a[i]]=i+1;
        seg.update(i,a[i]);
    }
    REP(i,Q){
        int query,l,r;
        cin>>query>>l>>r;
        l--;r--;
        if(query==1){
            swap(a[l],a[r]);
            swap(pos[a[l]],pos[a[r]]);
            seg.update(l,a[l]);
            seg.update(r,a[r]);
        }
        if(query==2){
            cout<<pos[seg.query(l,r+1)]<<endl;
        }
    }
}
0