結果

問題 No.875 Range Mindex Query
ユーザー どらら
提出日時 2019-09-07 11:07:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 268 ms / 2,000 ms
コード長 1,866 bytes
コンパイル時間 1,717 ms
コンパイル使用メモリ 171,472 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-26 06:20:52
合計ジャッジ時間 4,442 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

const static int INF = 10000000;

struct ST {
  int x, y;
  ST():x(INF),y(INF){}
  ST(int x, int y):x(x),y(y){}
};
ST combine(const ST& lhs, const ST& rhs){
  ST st;
  if(lhs.x < rhs.x){
    st = lhs;
  }else{
    st = rhs;
  }
  return st;
}
template<class S>
class SegmentTree {
  int N;
  vector<S> t;
  void build(){
    for(int i=N-1; i>0; i--){
      t[i] = combine(t[i<<1], t[i<<1|1]);
    }
  }
public:
  SegmentTree(int n_){
    N = 1;
    while(N < n_) N *= 2;
    t.resize(2*N);
    for(int i=N; i<2*N; i++){
      t[i] = S();
    }
    build();
  }
  SegmentTree(const vector<S>& v){
    N = 1;
    while(N < v.size()) N *= 2;
    t.resize(2*N);
    for(int i=0; i<v.size(); i++){
      t[i+N] = v[i];
    }
    build();
  }
  void modify(int p, S val){
    for(t[p+=N] = val; p>>=1;){
      t[p] = combine(t[p<<1], t[p<<1|1]);
    }
  }
  S query(int l, int r){
    S resl, resr;
    for(l+=N, r+=N; l<r; l>>=1, r>>=1){
      if(l&1) resl = combine(resl, t[l++]);
      if(r&1) resr = combine(t[--r], resr);
    }
    return combine(resl, resr);
  }
};


int main(){
  int N, Q;
  cin >> N >> Q;

  SegmentTree<ST> segtree(N);

  rep(i,N){
    int a;
    cin >> a;
    segtree.modify(i,ST(a,i));
  }
  rep(i,Q){
    int x, l, r;
    cin >> x >> l >> r;
    l--;
    r--;
    if(x == 1){
      ST lhs = segtree.query(l,l+1);
      ST rhs = segtree.query(r,r+1);
      swap(lhs.y, rhs.y);
      segtree.modify(l,rhs);
      segtree.modify(r,lhs);
    }else{
      ST ret = segtree.query(l,r+1);
      cout << ret.y+1 << endl;
    }
  }
  
  return 0;
}
0