#633897 (C++17) No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ

• 問題: No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
• ユーザー: Haar
• 提出日時: 2021-03-25 17:55:42
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 6,563 bytes
• コンパイル時間: 2,467 ms
• コンパイル使用メモリ: 191,564 KB
• 最終ジャッジ日時: 2025-01-19 21:39:11
• ジャッジサーバーID （参考情報）: judge2 / judge5

コンパイルメッセージ

/home/haar/Documents/kyopro-lib/Mylib/AlgebraicStructure/Monoid/sum.cpp: In instantiation of ‘haar_lib::sum_monoid<T>::value_type haar_lib::sum_monoid<T>::operator()(value_type, value_type) const [with T = std::pair<long int, long int>; value_type = std::pair<long int, long int>]’:
/home/haar/Documents/kyopro-lib/Mylib/DataStructure/SegmentTree/lazy_segment_tree.cpp:104:29:   required from ‘haar_lib::lazy_segment_tree<Monoid>::value_type_get haar_lib::lazy_segment_tree<Monoid>::fold(int, int) [with Monoid = haar_lib::update_sum<haar_lib::update_monoid<std::pair<long int, long int> >, haar_lib::sum_monoid<std::pair<long int, long int> > >; value_type_get = std::pair<long int, long int>]’
main.cpp:38:29:   required from here
/home/haar/Documents/kyopro-lib/Mylib/AlgebraicStructure/Monoid/sum.cpp:8:71: error: no match for ‘operator+’ (operand types are ‘haar_lib::sum_monoid<std::pair<long int, long int> >::value_type’ {aka ‘std::pair<long int, long int>’} and ‘haar_lib::sum_monoid<std::pair<long int, long int> >::value_type’ {aka ‘std::pair<long int, long int>’})
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from main.cpp:1:
/usr/include/c++/13/bits/stl_iterator.h:634:5: note: candidate: ‘template<class _Iterator> constexpr std::reverse_iterator<_Iterator> std::operator+(typename reverse_iterator<_Iterator>::difference_type, const reverse_iterator<_Iterator>&)’
  634 |     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
      |     ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:634:5: note:   template argument deduction/substitution failed:
/home/haar/Documents/kyopro-lib/Mylib/AlgebraicStructure/Monoid/sum.cpp:8:71: note:   ‘haar_lib::sum_monoid<std::pair<long int, long int> >::value_type’ {aka ‘std::pair<long int, long int>’} is not deriv

ソースコード

#line 1 "main.cpp"
#include <bits/stdc++.h>

#line 4 "/home/haar/Documents/kyopro-lib/Mylib/DataStructure/SegmentTree/lazy_segment_tree.cpp"

namespace haar_lib {
  template <typename Monoid>
  class lazy_segment_tree {
  public:
    using monoid_get = typename Monoid::monoid_get;
    using monoid_update = typename Monoid::monoid_update;
    using value_type_get = typename monoid_get::value_type;
    using value_type_update = typename monoid_update::value_type;

  private:
    Monoid M_;
    monoid_get M_get_;
    monoid_update M_update_;

    int depth_, size_, hsize_;
    std::vector<value_type_get> data_;
    std::vector<value_type_update> lazy_;

    void propagate(int i){
      if(lazy_[i] == M_update_()) return;
      if(i < hsize_){
        lazy_[i << 1 | 0] = M_update_(lazy_[i], lazy_[i << 1 | 0]);
        lazy_[i << 1 | 1] = M_update_(lazy_[i], lazy_[i << 1 | 1]);
      }
      const int len = hsize_ >> (31 - __builtin_clz(i));
      data_[i] = M_(data_[i], lazy_[i], len);
      lazy_[i] = M_update_();
    }

    void propagate_top_down(int i){
      std::vector<int> temp;
      while(i > 1){
        i >>= 1;
        temp.push_back(i);
      }

      for(auto it = temp.rbegin(); it != temp.rend(); ++it) propagate(*it);
    }

    void bottom_up(int i){
      while(i > 1){
        i >>= 1;
        propagate(i << 1 | 0);
        propagate(i << 1 | 1);
        data_[i] = M_get_(data_[i << 1 | 0], data_[i << 1 | 1]);
      }
    }

  public:
    lazy_segment_tree(){}
    lazy_segment_tree(int n):
      depth_(n > 1 ? 32 - __builtin_clz(n - 1) + 1 : 1),
      size_(1 << depth_),
      hsize_(size_ / 2),
      data_(size_, M_get_()),
      lazy_(size_, M_update_())
    {}

    void update(int l, int r, const value_type_update &x){
      assert(0 <= l and l <= r and r <= hsize_);
      propagate_top_down(l + hsize_);
      if(r < hsize_) propagate_top_down(r + hsize_);

      int L = l + hsize_, R = r + hsize_;

      while(L < R){
        if(R & 1){
          --R;
          lazy_[R] = M_update_(x, lazy_[R]);
          propagate(R);
        }
        if(L & 1){
          lazy_[L] = M_update_(x, lazy_[L]);
          propagate(L);
          ++L;
        }
        L >>= 1;
        R >>= 1;
      }

      bottom_up(l + hsize_);
      if(r < hsize_) bottom_up(r + hsize_);
    }

    void update(int i, const value_type_update &x){update(i, i + 1, x);}

    value_type_get fold(int l, int r){
      assert(0 <= l and l <= r and r <= hsize_);
      propagate_top_down(l + hsize_);
      if(r < hsize_) propagate_top_down(r + hsize_);

      value_type_get ret_left = M_get_(), ret_right = M_get_();

      int L = l + hsize_, R = r + hsize_;

      while(L < R){
        if(R & 1){
          --R;
          propagate(R);
          ret_right = M_get_(data_[R], ret_right);
        }
        if(L & 1){
          propagate(L);
          ret_left = M_get_(ret_left, data_[L]);
          ++L;
        }
        L >>= 1;
        R >>= 1;
      }

      return M_get_(ret_left, ret_right);
    }

    value_type_get fold_all(){
      return fold(0, hsize_);
    }

    value_type_get operator[](int i){return fold(i, i + 1);}

    template <typename T>
    void init(const T &val){
      init_with_vector(std::vector<T>(hsize_, val));
    }

    template <typename T>
    void init_with_vector(const std::vector<T> &val){
      data_.assign(size_, M_get_());
      lazy_.assign(size_, M_update_());
      for(int i = 0; i < (int)val.size(); ++i) data_[hsize_ + i] = (value_type_get)val[i];
      for(int i = hsize_; --i > 0;) data_[i] = M_get_(data_[i << 1 | 0], data_[i << 1 | 1]);
    }
  };
}
#line 3 "/home/haar/Documents/kyopro-lib/Mylib/AlgebraicStructure/Monoid/pair.cpp"

namespace haar_lib {
  template <typename Monoid1, typename Monoid2>
  struct pair_monoid {
    using value_type = std::pair<typename Monoid1::value_type, typename Monoid2::value_type>;
    const static Monoid1 M1;
    const static Monoid2 M2;

    value_type operator()() const {
      return {M1(), M2()};
    }

    value_type operator()(const value_type &a, const value_type &b) const {
      return {M1(a.first, b.first), M2(a.second, b.second)};
    }
  };
}
#line 2 "/home/haar/Documents/kyopro-lib/Mylib/AlgebraicStructure/Monoid/sum.cpp"

namespace haar_lib {
  template <typename T>
  struct sum_monoid {
    using value_type = T;
    value_type operator()() const {return T();}
    value_type operator()(value_type a, value_type b) const {return a + b;}
  };
}
#line 2 "/home/haar/Documents/kyopro-lib/Mylib/AlgebraicStructure/Monoid/update.cpp"
#include <optional>

namespace haar_lib {
  template <typename T>
  struct update_monoid {
    using value_type = std::optional<T>;
    value_type operator()() const {return std::nullopt;}
    value_type operator()(const value_type &a, const value_type &b) const {return (a ? a : b);}
  };
}
#line 2 "/home/haar/Documents/kyopro-lib/Mylib/AlgebraicStructure/MonoidAction/update_sum.cpp"

namespace haar_lib {
  template <typename MonoidUpdate, typename MonoidGet>
  struct update_sum {
    using monoid_get = MonoidGet;
    using monoid_update = MonoidUpdate;
    using value_type_get = typename MonoidGet::value_type;
    using value_type_update = typename MonoidUpdate::value_type;

    value_type_get operator()(value_type_get a, value_type_update b, int len) const {
      return b ? *b * len : a;
    }
  };
}
#line 8 "main.cpp"


template <typename T, typename U>
std::pair<T, U> operator+(const std::pair<T, U> &a, const std::pair<T, U> &b){
  return std::make_pair(a.first + b.first, a.second + b.second);
}

template <typename T, typename U, typename V>
std::pair<T, U> operator*(const std::pair<T, U> &a, V v){
  return std::make_pair(a.first * v, a.second * v);
}


using namespace haar_lib;

int main(){
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);

  int N, Q; std::cin >> N >> Q;

  lazy_segment_tree<update_sum<update_monoid<std::pair<int64_t, int64_t>>, sum_monoid<std::pair<int64_t, int64_t>>>> seg(N);

  int64_t score_a = 0, score_b = 0;

  for(int i = 0; i < Q; ++i){
    int x, l, r; std::cin >> x >> l >> r;

    switch(x){
    case 0: {
      auto [a, b] = seg.fold(l, r + 1);
      if(a > b) score_a += a;
      if(a < b) score_b += b;
      break;
    }
    case 1: {
      seg.update(l, r + 1, std::make_pair(1, 0));
      break;
    }
    case 2: {
      seg.update(l, r + 1, std::make_pair(0, 1));
      break;
    }
    }
  }

  auto [a, b] = seg.fold_all();
  score_a += a;
  score_b += b;

  std::cout << score_a << " " << score_b << "\n";

  return 0;
}