#376198 (C++17) No.875 Range Mindex Query

• 問題: No.875 Range Mindex Query
• ユーザー: rsk0315
• 提出日時: 2019-09-06 21:29:58
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 85 ms / 2,000 ms
• コード長: 5,429 bytes
• コンパイル時間: 698 ms
• コンパイル使用メモリ: 61,696 KB
• 実行使用メモリ: 10,624 KB
• 最終ジャッジ日時: 2024-06-24 16:49:43
• 合計ジャッジ時間: 2,287 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	78 ms; 8,832 KB
testcase_12	AC	63 ms; 7,296 KB
testcase_13	AC	57 ms; 9,984 KB
testcase_14	AC	56 ms; 9,600 KB
testcase_15	AC	75 ms; 10,112 KB
testcase_16	AC	80 ms; 10,240 KB
testcase_17	AC	85 ms; 10,624 KB
testcase_18	AC	81 ms; 10,368 KB

ソースコード

#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <utility>
#include <limits>

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
// constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }

template <
  typename Monoid,
  typename Container = std::vector<typename Monoid::first_type>
>
class basic_segment_tree {
public:
  using size_type = size_t;
  using first_type = typename Monoid::first_type;
  using second_type = typename Monoid::second_type;
  using value_type = first_type;
  using binary_operation = typename Monoid::binary_operation;
  using external_binary_operation = typename Monoid::external_binary_operation;
  using container = Container;

private:
  size_type M_base_size;
  binary_operation M_op1;
  external_binary_operation M_op2;
  container M_c;

  template <typename Predicate>
  size_type M_search_root(Predicate pred, value_type& x) const {
    size_type n = M_base_size;
    size_type l = n;
    size_type r = n+n;
    size_type v = r;
    std::vector<size_type> rs;
    x = M_op1.identity;
    while (l < r) {
      if (l & 1) {
        if (!pred(M_op1(x, M_c[l]))) return l;
        x = M_op1(x, M_c[l++]);
      }
      if (r & 1) rs.push_back(--r);
      l >>= 1;
      r >>= 1;
    }
    while (!rs.empty()) {
      size_type r = rs.back();
      rs.pop_back();
      if (!pred(M_op1(x, M_c[r]))) return r;
      x = M_op1(x, M_c[r]);
    }
    return v;
  }

  template <typename Predicate>
  size_type M_search_leaf(Predicate pred, size_type v, value_type& x) const {
    size_type n = M_base_size;
    while (v < n) {
      size_type c = v << 1;
      if (pred(M_op1(x, M_c[c]))) {
        x = M_op1(x, M_c[c]);
        c |= 1;
      }
      v = c;
    }
    return v - n;
  }

public:
  basic_segment_tree() = default;
  basic_segment_tree(basic_segment_tree const&) = default;
  basic_segment_tree(basic_segment_tree&&) = default;

  basic_segment_tree(size_type n, first_type const& x = binary_operation().identity):
    M_base_size(n),
    M_op1(binary_operation()),
    M_op2(external_binary_operation()),
    M_c(n+n, x)
  {
    for (size_type i = n; i--;)
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
  }

  template <typename InputIt>
  basic_segment_tree(InputIt first, InputIt last):
    M_op1(binary_operation()), M_op2(external_binary_operation())
  { assign(first, last); }

  basic_segment_tree& operator =(basic_segment_tree const&) = default;
  basic_segment_tree& operator =(basic_segment_tree&&) = default;

  void assign(size_type n, value_type const& x) {
    M_base_size = n;
    M_c.assign(n+n, x);
    for (size_type i = n; i--;)
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
  }
  template <typename InputIt>
  void assign(InputIt first, InputIt last) {
    container tmp(first, last);
    M_base_size = tmp.size();
    M_c.resize(M_base_size);
    M_c.insert(M_c.end(), tmp.begin(), tmp.end());
    for (size_type i = M_base_size; i--;)
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
  }

  void modify(size_type i, second_type const& x) {
    i += M_base_size;
    M_c[i] = M_op2(M_c[i], x);
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
    }
  }

  void assign_at(size_type i, value_type const& x) {
    i += M_base_size;
    M_c[i] = x;
    while (i > 1) {
      i >>= 1;
      M_c[i] = M_op1(M_c[i<<1|0], M_c[i<<1|1]);
    }
  }

  value_type const& operator [](size_type i) const { return M_c[i + M_base_size]; }

  value_type accumulate(size_type l, size_type r) {
    first_type resl = M_op1.identity;
    first_type resr = resl;
    l += M_base_size;
    r += M_base_size;
    while (l < r) {
      if (l & 1) resl = M_op1(resl, M_c[l++]);
      if (r & 1) resr = M_op1(M_c[--r], resr);
      l >>= 1;
      r >>= 1;
    }
    return M_op1(resl, resr);
  }

  template <typename Predicate>
  std::pair<size_type, value_type> partition_point(Predicate pred) const {
    value_type value;
    size_type root = M_search_root(pred, value);
    size_type bound = M_search_leaf(pred, root, value);
    return {bound, value};
  }
};

template <typename Tp>
struct range_min_single_assign {
  using first_type = std::pair<Tp, size_t>;
  using second_type = Tp;
  struct binary_operation {
    first_type identity{std::numeric_limits<Tp>::max(), -1_zu};
    first_type operator ()(first_type const& x, first_type const& y) const {
      return std::min(x, y);
    }
  };
  struct external_binary_operation {
    first_type operator ()(first_type const& x, second_type const& y) const {
      return {y, x.second};
    }
  };
};

int main() {
  size_t n, q;
  scanf("%zu %zu", &n, &q);

  std::vector<std::pair<int, size_t>> a(n);
  for (size_t i = 0; i < n; ++i) {
    scanf("%d", &a[i].first);
    a[i].second = i+1;
  }

  basic_segment_tree<range_min_single_assign<int>> st(a.begin(), a.end());

  for (size_t i = 0; i < q; ++i) {
    int t;
    scanf("%d", &t);

    if (t == 1) {
      size_t l, r;
      scanf("%zu %zu", &l, &r);
      --l, --r;
      int al = st[l].first;
      int ar = st[r].first;
      st.modify(l, ar);
      st.modify(r, al);
    } else if (t == 2) {
      size_t l, r;
      scanf("%zu %zu", &l, &r);
      --l, --r;
      printf("%zu\n", st.accumulate(l, r+1).second);
    }
  }
}