結果

問題 No.875 Range Mindex Query
ユーザー otamay6otamay6
提出日時 2019-09-06 21:42:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 260 ms / 2,000 ms
コード長 1,784 bytes
コンパイル時間 1,582 ms
コンパイル使用メモリ 173,036 KB
実行使用メモリ 5,016 KB
最終ジャッジ日時 2023-09-06 23:17:47
合計ジャッジ時間 4,447 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 3 ms
4,376 KB
testcase_02 AC 3 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 3 ms
4,376 KB
testcase_11 AC 183 ms
4,572 KB
testcase_12 AC 153 ms
4,376 KB
testcase_13 AC 131 ms
5,016 KB
testcase_14 AC 128 ms
4,684 KB
testcase_15 AC 176 ms
5,008 KB
testcase_16 AC 238 ms
4,940 KB
testcase_17 AC 260 ms
5,008 KB
testcase_18 AC 245 ms
4,936 KB
権限があれば一括ダウンロードができます

ソースコード

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