#1036809 (C++23) No.833 かっこいい電車

• 問題: No.833 かっこいい電車
• ユーザー: cutmdo
• 提出日時: 2025-01-23 16:34:08
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 300 ms / 2,000 ms
• コード長: 14,424 bytes
• コンパイル時間: 1,498 ms
• コンパイル使用メモリ: 126,444 KB
• 実行使用メモリ: 14,976 KB
• 最終ジャッジ日時: 2025-01-23 16:34:20
• 合計ジャッジ時間: 6,822 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 30

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#define PROBLEM "https://yukicoder.me/problems/no/833"
#include <iostream>
#include <numeric>
#include <ranges>
#include <vector>
#include <vector>
#include <utility>
#include <deque>
#include <iostream>
namespace mtd {  template <class S,                S element,              class op                >  requires std::is_invocable_r_v<S, op, S, S>  
    struct Monoid {    using value_type = S;    constexpr static S _element = element;    using op_type = op;    S m_val;    constexpr Monoid(S val) : 
    m_val(val) {}    constexpr Monoid() : Monoid(element) {}    constexpr Monoid binaryOperation(const Monoid& m2) const {      return op()(m_val, m2
    .m_val);    }    friend std::ostream& operator<<(std::ostream& os,                                    const Monoid<S, element, op>& m) {      
    return os << m.m_val;    }  };  namespace __detail {    template <typename T, template <typename, auto, typename> typename S>    concept 
    is_monoid_specialization_of = requires {      typename std::enable_if_t<std::is_same_v<          T, S<typename T::value_type, T::_element, 
    typename T::op_type>>>;    };  }    template <typename M>  concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;}  
namespace mtd {  template <monoid Monoid, monoid MonoidOp, class op>  class LazySegmentTree {  private:    const int m_size;    std::vector<Monoid> 
    m_node;    std::vector<MonoidOp> m_lazy;    using S = decltype(Monoid().m_val);    constexpr int calcSize(int n) const {      int size = 1;      
    while (size < n) { size <<= 1; }      return size;    }    constexpr auto _lazy_update(int i, const MonoidOp& val) {      if (i >= (m_size << 1) - 
    1) { return; }      m_lazy[i] = m_lazy[i].binaryOperation(val);    }    constexpr auto _propagate(int i) {      m_node[i] = op()(m_node[i], 
    m_lazy[i]);      _lazy_update((i << 1) + 1, m_lazy[i]);      _lazy_update((i << 1) + 2, m_lazy[i]);      m_lazy[i] = MonoidOp();    }    constexpr 
    auto _update(int l, int r, int k, int nl, int nr,                           const MonoidOp& m) {      _propagate(k);      if (nr < l || r < nl) { 
    return; }      if (l <= nl && nr <= r) {        _lazy_update(k, m);        _propagate(k);        return;      }      _update(l, r, (k << 1) + 1, 
    nl, (nl + nr) >> 1, m);      _update(l, r, (k << 1) + 2, ((nl + nr) >> 1) + 1, nr, m);      m_node[k] = m_node[(k << 1) + 1].binaryOperation
    (m_node[(k << 1) + 2]);    }    constexpr auto _query(int l, int r, int k, int nl, int nr) {      _propagate(k);      if (nr < l || r < nl) { 
    return Monoid(); }      if (l <= nl && nr <= r) { return m_node[k]; }      auto l_val = _query(l, r, (k << 1) + 1, nl, (nl + nr) >> 1);      auto 
    r_val = _query(l, r, (k << 1) + 2, ((nl + nr) >> 1) + 1, nr);      return l_val.binaryOperation(r_val);    }    constexpr auto _construct(const 
    std::vector<S>& vec) {      for (unsigned int i = 0; i < vec.size(); ++i) {        m_node[i + m_size - 1] = Monoid(vec[i]);      }      for (int i 
    = m_size - 2; i >= 0; --i) {        m_node[i] =            m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1LL]);      }    }  public:    
    constexpr LazySegmentTree(int n)        : m_size(calcSize(n)),          m_node((m_size << 1) - 1),          m_lazy((m_size << 1) - 1) {}    
    constexpr LazySegmentTree(int n, const std::vector<S>& vec)        : LazySegmentTree(n) {      _construct(vec);    }    constexpr auto update(int 
    l, int r, const MonoidOp& val) {      _update(l, r, 0, 0, m_size - 1, val);    }    constexpr auto query(int l, int r) {      return _query(l, r, 
    0, 0, m_size - 1).m_val;    }    /*     * f([l, r]) = true となる最大のr     * judge: (Monoid) -> bool     **/    template <class F>    constexpr 
    auto max_right(int _l, const F& judge) {      if (!judge(Monoid())) {        throw std::runtime_error("SegmentTree.max_right.judge(e) must be 
    true");      }      query(_l, m_size - 1);      auto l = std::max(_l, 0) + m_size;      auto r = 2 * m_size - 1;      auto lm = Monoid();      
    while (l <= r) {        if (l & 1) {          auto next = lm.binaryOperation(m_node[l - 1]);          if (!judge(next)) {            auto itr = l; 
               while (itr < m_size) {              _propagate(itr - 1);              auto litr = 2 * itr;              auto ritr = 2 * itr + 1;       
           _propagate(litr - 1);              auto lval = lm.binaryOperation(m_node[litr - 1]);              if (!judge(lval)) {                itr = 
    litr;              } else {                itr = ritr;                std::swap(lm, lval);              }            }            return itr - 
    m_size - 1;          }          std::swap(lm, next);          ++l;        }        l >>= 1, r >>= 1;      }      return m_size - 1;    }    /*    
     * f([l, r]) = true となる最小のl     * judge: (Monoid) -> bool     **/    template <class F>    constexpr auto min_left(int _r, const F& judge) { 
         if (!judge(Monoid())) {        throw std::runtime_error("SegmentTree.min_left.judge(e) must be true");      }      query(0, _r);      auto l 
    = m_size;      auto r = std::min(_r, m_size - 1) + m_size;      auto rm = Monoid();      while (l <= r) {        if (l & 1) { ++l; }        if (!
    (r & 1) || (_r == m_size - 1 && r == 1)) {          auto next = m_node[r - 1].binaryOperation(rm);          if (!judge(next)) {            auto 
    itr = r;            while (itr < m_size) {              _propagate(itr);              auto litr = 2 * itr;              auto ritr = 2 * itr + 1;  
                _propagate(ritr - 1);              auto rval = m_node[ritr - 1].binaryOperation(rm);              if (!judge(rval)) {                
    itr = ritr;              } else {                itr = litr;                std::swap(rm, rval);              }            }            return itr 
    - m_size + 1;          }          std::swap(rm, next);          --r;        }        l >>= 1, r >>= 1;      }      return 0;    }    constexpr 
    auto debug() {      for (int i = 0; i < (m_size << 1) - 1; ++i) { _propagate(i); }      for (int i = 0; i < m_size; ++i) {        std::cout << 
    m_node[m_size + i - 1] << " ";      }      std::cout << std::endl;    }  };  namespace type {    /* 各種頻出サンプル */    using P = std::pair
    <long long, long long>;    constexpr long long update_element = -1e18;    /*---- 要素 ----*/    using M_SUM = Monoid<P, P{0, 0}, decltype([](const 
    P& a, const P& b) {                           return P{a.first + b.first, a.second + b.second};                         })>;    using M_MIN = 
    Monoid<long long, static_cast<long long>(1e18),                         decltype([](long long a, long long b) {                           return 
    std::min(a, b);                         })>;    using M_MAX = Monoid<long long, static_cast<long long>(-1e18),                         decltype([]
    (long long a, long long b) {                           return std::max(a, b);                         })>;    /*---- 作用素 ----*/    using M_UP = 
    Monoid<long long, update_element,                        decltype([](long long a, long long b) {                          if (b == update_element) 
    { return a; }                          return b;                        })>;    using M_ADD =        Monoid<long long, static_cast<long long>(0), 
                  decltype([](long long a, long long b) { return a + b; })>;    /*---- 作用 ----*/    using OP_SUM_UP = decltype([](const M_SUM& m, 
    const M_UP& m2) {      if (m2.m_val == update_element) { return m; }      return M_SUM(P{m.m_val.second * m2.m_val, m.m_val.second});    });    
    using OP_MIN_UP = decltype([](const M_MIN& m, const M_UP& m2) {      if (m2.m_val == update_element) { return m; }      return M_MIN(m2.m_val);   
     });    using OP_MAX_UP = decltype([](const M_MAX& m, const M_UP& m2) {      if (m2.m_val == update_element) { return m; }      return M_MAX(m2
    .m_val);    });    using OP_SUM_ADD = decltype([](const M_SUM& m, const M_ADD& m2) {      return M_SUM(          P{m.m_val.first + m.m_val.second 
    * m2.m_val, m.m_val.second});    });    using OP_MIN_ADD = decltype([](const M_MIN& m, const M_ADD& m2) {      return M_MIN{m.m_val + m2.m_val};  
      });    using OP_MAX_ADD = decltype([](const M_MAX& m, const M_ADD& m2) {      return M_MAX{m.m_val + m2.m_val};    });  }  }  
namespace mtd {  template <monoid Monoid>  class SegmentTree {  private:    const int m_size;    std::vector<Monoid> m_node;    using S = decltype
    (Monoid().m_val);    constexpr int calcSize(int n) const {      int size = 1;      while (size < n) { size <<= 1; }      return size;    }    
    template <class Lambda>    constexpr auto _update_op(int itr, Monoid&& val, const Lambda& op) {      int i = itr + m_size - 1;      m_node[i] = op
    (m_node[i], std::forward<decltype(val)>(val));      while (i) {        i = (i - 1) >> 1;        m_node[i] = m_node[(i << 1) | 1].binaryOperation
    (m_node[(i + 1) << 1]);      }    }    constexpr auto _query(int _l, int _r) const {      auto l = std::max(_l, 0) + m_size;      auto r = std
    ::min(_r, m_size - 1) + m_size;      auto lm = Monoid();      auto rm = Monoid();      while (l <= r) {        if (l & 1) {          lm = lm
    .binaryOperation(m_node[l - 1]);          ++l;        }        if (!(r & 1)) {          rm = m_node[r - 1].binaryOperation(rm);          --r;     
       }        l >>= 1, r >>= 1;      }      return lm.binaryOperation(rm);    }    constexpr auto _construct(const std::vector<S>& vec) {      for 
    (unsigned int i = 0; i < vec.size(); ++i) {        m_node[i + m_size - 1] = Monoid(vec[i]);      }      for (int i = m_size - 2; i >= 0; --i) {   
         m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);      }    }  public:    SegmentTree(int n) : m_size(calcSize(n)), 
    m_node((m_size << 1) - 1) {}    SegmentTree(int n, const std::vector<S>& vec) : SegmentTree(n) {      _construct(vec);    }    template <class 
    Lambda>    constexpr auto update_op(int itr, Monoid&& val, const Lambda& op) {      return _update_op(itr, std::forward<Monoid>(val), op);    }   
     constexpr auto update(int itr, Monoid&& val) {      return update_op(itr, std::forward<Monoid>(val),                       [](const Monoid&, 
    const Monoid& m2) { return m2; });    }    constexpr auto add(int itr, Monoid&& val) {      return update_op(itr, std::forward<Monoid>(val),      
                     [](const Monoid& m1, const Monoid& m2) {                         return Monoid(m1.m_val + m2.m_val);                       });   
     }    constexpr auto query(int l, int r) const { return _query(l, r).m_val; }    constexpr auto query_all() const { return m_node[0].m_val; }    
    /*     * f([l, r]) = true となる最大のr     * judge: (Monoid) -> bool     **/    template <class F>    constexpr auto max_right(int _l, const F& 
    judge) const {      if (!judge(Monoid())) {        throw std::runtime_error("SegmentTree.max_right.judge(e) must be true");      }      auto l = 
    std::max(_l, 0) + m_size;      auto r = 2 * m_size - 1;      auto lm = Monoid();      while (l <= r) {        if (l & 1) {          auto next = lm
    .binaryOperation(m_node[l - 1]);          if (!judge(next)) {            auto itr = l;            while (itr < m_size) {              auto litr = 
    2 * itr;              auto ritr = 2 * itr + 1;              auto lval = lm.binaryOperation(m_node[litr - 1]);              if (!judge(lval)) {    
                itr = litr;              } else {                itr = ritr;                std::swap(lm, lval);              }            }          
      return itr - m_size - 1;          }          std::swap(lm, next);          ++l;        }        l >>= 1, r >>= 1;      }      return m_size - 1; 
       }    /*     * f([l, r]) = true となる最小のl     * judge: (Monoid) -> bool     **/    template <class F>    constexpr auto min_left(int _r, 
    const F& judge) const {      if (!judge(Monoid())) {        throw std::runtime_error("SegmentTree.min_left.judge(e) must be true");      }      
    auto l = m_size;      auto r = std::min(_r, m_size - 1) + m_size;      auto rm = Monoid();      while (l <= r) {        if (l & 1) { ++l; }       
     if (!(r & 1) || (_r == m_size - 1 && r == 1)) {          auto next = m_node[r - 1].binaryOperation(rm);          if (!judge(next)) {            
    auto itr = r;            while (itr < m_size) {              auto litr = 2 * itr;              auto ritr = 2 * itr + 1;              auto rval = 
    m_node[ritr - 1].binaryOperation(rm);              if (!judge(rval)) {                itr = ritr;              } else {                itr = litr; 
                   std::swap(rm, rval);              }            }            return itr - m_size + 1;          }          std::swap(rm, next);      
        --r;        }        l >>= 1, r >>= 1;      }      return 0;    }    constexpr auto debug() const {      for (int i = 0; i < m_size; ++i) {   
         std::cout << m_node[m_size + i - 1] << " ";      }      std::cout << std::endl;    }  };}  
using ll = long long;
signed main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(0);
  int n, q;
  std::cin >> n >> q;
  std::vector<ll> a(n);
  for (auto i : std::views::iota(0, n)) { std::cin >> a[i]; }
  std::vector<ll> v(n);
  std::iota(v.begin(), v.end(), 0);
  auto segtree1 = mtd::LazySegmentTree<mtd::type::M_MIN, mtd::type::M_UP,
                                       mtd::type::OP_MIN_UP>(n, v);
  auto segtree2 = mtd::LazySegmentTree<mtd::type::M_MAX, mtd::type::M_UP,
                                       mtd::type::OP_MAX_UP>(n, v);
  auto range = [&](int i) {
    auto val = segtree1.query(i, i);
    auto judge_l = [&](const mtd::type::M_MIN& m) { return m.m_val >= val; };
    auto judge_r = [&](const mtd::type::M_MAX& m) { return m.m_val <= val; };
    auto l = segtree1.min_left(i, judge_l);
    auto r = segtree2.max_right(i, judge_r);
    return std::make_tuple(l, r);
  };
  for (auto i : std::views::iota(0, n)) { range(i); }
  auto op = [](ll a, ll b) { return a + b; };
  using M = mtd::Monoid<ll, 0LL, decltype(op)>;
  auto segtree3 = mtd::SegmentTree<M>(n, a);
  for ([[maybe_unused]] auto _ : std::views::iota(0, q)) {
    int t, x;
    std::cin >> t >> x;
    --x;
    if (t == 1) {
      auto val = segtree1.query(x, x);
      auto [l, r] = range(x + 1);
      segtree1.update(l, r, val);
      segtree2.update(l, r, val);
    } else if (t == 2) {
      auto [l, r] = range(x + 1);
      segtree1.update(x + 1, r, x + 1);
      segtree2.update(x + 1, r, x + 1);
    } else if (t == 3) {
      segtree3.add(x, 1);
    } else {
      auto [l, r] = range(x);
      std::cout << segtree3.query(l, r) << std::endl;
    }
  }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX