結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー Haar
提出日時 2020-02-08 17:31:17
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 453 ms / 2,000 ms
コード長 3,065 bytes
記録
コンパイル時間 4,168 ms
コンパイル使用メモリ 197,424 KB
最終ジャッジ日時 2025-01-08 23:13:35
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:86:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |   int N, Q; scanf("%d %d", &N, &Q);
      |             ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:92:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   92 |     int x; scanf("%d", &x);
      |            ~~~~~^~~~~~~~~~
main.cpp:101:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  101 |       int l, r; scanf("%d %d", &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:113:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  113 |       int l, r; scanf("%d %d", &l, &r);
      |                 ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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