結果

問題 No.875 Range Mindex Query
ユーザー HaarHaar
提出日時 2020-02-08 17:31:17
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 3,065 bytes
コンパイル時間 2,140 ms
コンパイル使用メモリ 207,972 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-25 08:52:57
合計ジャッジ時間 4,568 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 3 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 149 ms
6,944 KB
testcase_12 AC 125 ms
6,944 KB
testcase_13 AC 99 ms
6,940 KB
testcase_14 AC 100 ms
6,940 KB
testcase_15 AC 144 ms
6,940 KB
testcase_16 AC 200 ms
6,940 KB
testcase_17 AC 217 ms
6,944 KB
testcase_18 AC 206 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

template <typename Monoid>
class SegmentTree{
  using value_type = typename Monoid::value_type;
  
protected:
  const int depth, size, hsize;
  std::vector<value_type> data;

public:
  SegmentTree(int n):
    depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1),
    size((1 << depth) - 1),
    hsize(size / 2 + 1),
    data(size + 1, Monoid::id())
  {}

  inline auto operator[](int i) const {return at(i);}
  inline auto at(int i) const {return data[hsize + i];}
  
  inline auto get(int x, int y) const { // [x,y)
    value_type ret_left = Monoid::id();
    value_type ret_right = Monoid::id();
    
    int l = x + hsize, r = y + hsize;
    while(l < r){
      if(r & 1) ret_right = Monoid::op(data[--r], ret_right);
      if(l & 1) ret_left = Monoid::op(ret_left, data[l++]);
      l >>= 1, r >>= 1;
    }
    
    return Monoid::op(ret_left, ret_right);
  }

  inline void update(int i, const value_type &x){
    i += hsize;
    data[i] = x;
    while(i > 1) i >>= 1, data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init_with_vector(const std::vector<T> &val){
    data.assign(size + 1, Monoid::id());
    for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i];
    for(int i = hsize-1; i >= 1; --i) data[i] = Monoid::op(data[i << 1 | 0], data[i << 1 | 1]);
  }

  template <typename T>
  inline void init(const T &val){
    init_with_vector(std::vector<value_type>(hsize, val));
  }  

  auto debug(){
    return data;
  }
};



template <typename T, typename = void>
struct MinMonoid{
  using value_type = T;
  static value_type INF;
  constexpr inline static value_type id(){return INF;}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return std::min(a, b);}
};

template <typename T>
struct MinMonoid<T, typename std::enable_if<std::numeric_limits<T>::is_bounded>::type>{
  using value_type = T;
  constexpr inline static value_type id(){return std::numeric_limits<T>::max();}
  constexpr inline static value_type op(const value_type &a, const value_type &b){return std::min(a, b);}
};

using Mon = MinMonoid<std::pair<int, int>>;
template <> std::pair<int, int> MinMonoid<std::pair<int, int>>::INF = std::make_pair(std::numeric_limits<int>::max(), std::numeric_limits<int>::max());

int get_int(){
  int ret; std::cin >> ret;
  return ret;
}


int main(){
  int N, Q; scanf("%d %d", &N, &Q);

  SegmentTree<Mon> seg(N);

  std::vector<Mon::value_type> a(N);
  for(int i = 0; i < N; ++i){
    int x; scanf("%d", &x);
    a[i] = std::make_pair(x, i);
  }

  seg.init_with_vector(a);

  for(int i = 0; i < Q; ++i){
    switch(get_int()){
    case 1: {
      int l, r; scanf("%d %d", &l, &r);
      --l, --r;

      auto x = seg[l].first;
      auto y = seg[r].first;

      seg.update(l, std::make_pair(y, l));
      seg.update(r, std::make_pair(x, r));

      break;
    }
    case 2: {
      int l, r; scanf("%d %d", &l, &r);
      --l, --r;

      printf("%d\n", seg.get(l, r+1).second + 1);

      break;
    }
    }
  }

  return 0;
}
0