結果

問題 No.875 Range Mindex Query
ユーザー HaarHaar
提出日時 2020-02-06 14:17:24
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 247 ms / 2,000 ms
コード長 2,741 bytes
コンパイル時間 2,041 ms
コンパイル使用メモリ 207,800 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-25 06:48:30
合計ジャッジ時間 4,743 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 3 ms
6,940 KB
testcase_02 AC 3 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 3 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 190 ms
6,944 KB
testcase_12 AC 156 ms
6,944 KB
testcase_13 AC 132 ms
6,940 KB
testcase_14 AC 128 ms
6,944 KB
testcase_15 AC 177 ms
6,944 KB
testcase_16 AC 239 ms
6,944 KB
testcase_17 AC 247 ms
6,944 KB
testcase_18 AC 244 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>


template <typename Monoid>
class SegmentTree{
protected:
  const int depth, size, hsize;
  std::vector<Monoid> 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)
    int l = x + hsize, r = y + hsize;
    Monoid ret = Monoid::id();
    while(l < r){ // must be commutative
      if(r & 1) ret = ret + data[--r];
      if(l & 1) ret = ret + data[l++];
      l >>= 1, r >>= 1;
    }
    return ret;
  }

  inline void update(int i, const Monoid &x){
    i += hsize;
    data[i] = x;
    while(i > 1) i >>= 1, data[i] = 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] = data[i << 1 | 0] + data[i << 1 | 1];
  }

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

  auto debug(){
    return data;
  }
};

template <typename T> struct MinMonoid{
  using value_type = T;

  T value;
  static T INF;

  MinMonoid(): value(){}
  MinMonoid(T value): value(value){}

  constexpr inline static MinMonoid id(){
    return INF;
  }

  friend inline MinMonoid operator+(const MinMonoid &a, const MinMonoid &b){
    return std::min(a.value, b.value);
  }

  friend std::ostream& operator<<(std::ostream &s, const MinMonoid &a){
    s << a.value;
    return s;
  }
};



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; std::cin >> N >> Q;

  SegmentTree<Mon> seg(N);

  std::vector<Mon> a(N);
  for(int i = 0; i < N; ++i){
    int x; std::cin >> x;
    a[i] = Mon(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; std::cin >> l >> r;
      --l, --r;

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

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

      break;
    }
    case 2: {
      int l, r; std::cin >> l >> r;
      --l, --r;

      std::cout << seg.get(l, r+1).value.second + 1 << std::endl;

      break;
    }
    }
  }

  return 0;
}
0