結果

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

ソースコード

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; scanf("%d %d", &N, &Q);

  SegmentTree<Mon> seg(N);

  std::vector<Mon> a(N);
  for(int i = 0; i < N; ++i){
    int x; scanf("%d", &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; scanf("%d %d", &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; scanf("%d %d", &l, &r);
      --l, --r;

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

      break;
    }
    }
  }

  return 0;
}
0