結果

問題 No.875 Range Mindex Query
コンテスト
ユーザー Haar
提出日時 2020-02-06 14:17:24
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 312 ms / 2,000 ms
コード長 2,741 bytes
記録
コンパイル時間 2,009 ms
コンパイル使用メモリ 199,972 KB
最終ジャッジ日時 2025-01-08 22:30:26
ジャッジサーバーID
（参考情報） 		judge5 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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