#278941 (C++11) No.235 めぐるはめぐる (5)

提出ソース
結果

問題	No.235 めぐるはめぐる (5)
ユーザー	lumc_
提出日時	2018-08-18 20:27:57
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	1,912 ms / 10,000 ms
コード長	16,039 bytes
コンパイル時間	3,095 ms
コンパイル使用メモリ	183,712 KB
実行使用メモリ	34,336 KB
最終ジャッジ日時	2024-11-06 20:18:57
合計ジャッジ時間	11,576 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,912 ms 33,684 KB
testcase_01	AC	990 ms 34,336 KB
testcase_02	AC	1,559 ms 33,788 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
#ifdef DEBUG
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << "{"; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; return o; }
#ifdef USE_COUT
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cout<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#else
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<__debug_tap<<"\n";}()
#endif
template<class T> inline void dump2D(T &d, size_t sizey, size_t sizex) { ostream&o=
#ifdef USE_COUT
  cout;
#else
  cerr;
#endif
  for(size_t i = 0; i < sizey; i++) { for(size_t j = 0; j < sizex; j++) o << d[i][j] << " "; o << endl; }
}
#else
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); return o; }
#define dump(...) (42)
#define dump2D(...) (42)
#endif
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
template<class T, class U> ostream & operator<<(ostream &o, pair<T, U> const &p) { o << "(" << p.first << ", " << p.second << ")"; return o; }
/// }}}--- ///

const ll mod = 1e9 + 7;
const int N = 2e5;
int n;

/// ModInt Library {{{ ///
template<long long mod = (long long)1e9 + 7>
struct ModInt{
private:
  long long extgcd(long long a, long long b, long long &x, long long &y) { long long d; return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d); }
  long long modinv(long long a) { long long x = 0, y = 0; extgcd(a, mod, x, y); return (x + mod) % mod; }
public:
  long long val;
  constexpr ModInt() : val(0) {}
  constexpr ModInt(long long val) : val((val % mod + mod) % mod) {}
  operator int() const { return val; }
  operator long long() const { return val; }
  ModInt operator+(ModInt const &rhs) const { return ModInt(val + rhs.val); }
  ModInt operator-(ModInt const &rhs) const { return ModInt(val - rhs.val); }
  ModInt operator*(ModInt const &rhs) const { return ModInt(val * rhs.val); }
  ModInt operator/(ModInt const &rhs) const { return ModInt(val * rhs.inv().val); }
  ModInt &operator+=(ModInt const &rhs) {
    val = ((val + rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator-=(ModInt const &rhs) {
    val = ((val - rhs.val) % mod + mod) % mod;
    return *this;
  }
  ModInt &operator*=(ModInt const &rhs) {
    val = (val * rhs.val % mod + mod) % mod;
    return *this;
  }
  ModInt &operator/=(ModInt const &rhs) {
    val = (val * rhs.inv().val % mod + mod) % mod;
    return *this;
  }
  ModInt operator++(int) {
    ModInt tmp = *this;
    val = val + 1;
    if(val >= mod) val = 0;
    return tmp;
  }
  ModInt operator--(int) {
    ModInt tmp = *this;
    val = val == 0 ? mod - 1 : val - 1;
    return tmp;
  }
  ModInt &operator++() {
    val = val + 1;
    if(val >= mod) val = 0;
    return *this;
  }
  ModInt &operator--() {
    val = val == 0 ? mod - 1 : val - 1;
    return *this;
  }
  ModInt operator-() const {
    return ModInt(mod - val);
  }
  bool operator==(const ModInt &rhs) const {
    return val == rhs.val;
  }
  bool operator!=(const ModInt &rhs) const {
    return val != rhs.val;
  }
  template<typename T> ModInt operator+(T const &rhs) const {
    return ModInt(val + rhs % mod);
  }
  template<typename T> ModInt operator-(T const &rhs) const {
    return ModInt(val - rhs % mod);
  }
  template<typename T> ModInt operator*(T const &rhs) const {
    return ModInt(val * (rhs % mod));
  }
  template<typename T> ModInt operator/(T const &rhs) const {
    return ModInt(val * modinv(rhs, mod));
  }
  template<typename T> ModInt &operator+=(T const &rhs) {
    val = ((val + rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator-=(T const &rhs) {
    val = ((val - rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator*=(T const &rhs) {
    val = (val * (rhs % mod) % mod + mod) % mod;
    return *this;
  }
  template<typename T> ModInt &operator/=(T const &rhs) {
    val = (val * modinv(rhs, mod) % mod + mod) % mod;
    return *this;
  }
  ModInt inv() const {
    return ModInt(modinv(val, mod));
  }
  friend ostream &operator<<(ostream &os, ModInt const &mv) { os << mv.val; return os; }
  friend constexpr ModInt operator+(long long a, ModInt const &mv) { return ModInt(a % mod + mv.val); }
  friend constexpr ModInt operator-(long long a, ModInt const &mv) { return ModInt(a % mod - mv.val); }
  friend constexpr ModInt operator*(long long a, ModInt const &mv) { return ModInt(a % mod * mv.val); }
  friend constexpr ModInt operator/(long long a, ModInt const &mv) { return ModInt(a % mod * mv.inv().val); }
};
/// }}}-- ///

using Int = ModInt<mod>;

/// --- Graph Template {{{ ///

template<class T>
struct Edge {
  int from, to; T cost;
  Edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};
template<class T>
using WeightedGraph = vector< vector< Edge<T> > >;
using UnWeightedGraph = vector< vector<int> >;

/// }}}--- ///

ll s[N], c[N];

// query(hi, lo, func, inclusive?)
// hld[i] : index on sequence
// WARN : build after adding edges!
/// --- HL-Decomposition Library {{{ ///

struct HLD {
  int n;
  vector<int> head;
  vector<int> sz;
  vector<int> dep;
  vector<int> par;
  vector<int> vid;
  int id = 0;
  UnWeightedGraph g; // tree
  HLD(int n): n(n), head(n), sz(n), dep(n), par(n), vid(n), g(n) {}
  HLD(UnWeightedGraph g, int root = 0): HLD(g.size()) { this->g = g; build(root); }
  int operator[](int i) { return vid[i]; }
  void addEdge(int a, int b) {
    g[a].emplace_back(b);
    g[b].emplace_back(a);
  }
  void build(int root = 0) {
    head[root] = root;
    dfs0(root, -1, 0); dfs1(root, -1);
  }
  int lca(int a, int b) {
    while(1) {
      if(vid[a] > vid[b]) swap(a, b);
      if(head[a] == head[b]) return a;
      b = par[head[b]];
    }
  }
  void query(int hi, int lo, function<void(int, int)> f, bool inclusive = true) {
    while(lo != -1 && dep[lo] >= dep[hi]) {
      int nex = max(vid[head[lo]], vid[hi]);
      f(nex + (nex == vid[hi] && !inclusive), vid[lo] + 1);
      lo = par[head[lo]];
    }
  }
private:
  void dfs0(int i, int p, int d) {
    par[i] = p;
    sz[i] = 1;
    dep[i] = d;
    for(int &j : g[i]) if(j != p) {
      dfs0(j, i, d + 1);
      sz[i] += sz[j];
      if(sz[j] > sz[g[i][0]]) {
        swap(g[i][0], j);
      }
    }
  }
  void dfs1(int i, int p) {
    vid[i] = id++;
    for(int j : g[i]) if(j != p) {
      head[j] = j == g[i][0] ? head[i] : j;
      dfs1(j, i);
    }
  }
};

/// }}}--- ///

vector<Int> csum(N);
Int getC(int l, int r) {
  Int res = csum[r-1];
  if(l-1>=0) res -= csum[l-1];
  return res;
}

// NOTE : query in range!
/// --- LazySegmentTree Library {{{ ///

// struct Monoid {
//   using T = _underlying_set_;
//   static T op(const T& a, const T& b) { return _a_op_b_; }
//   static constexpr T identity() { return _identity_element_; }
// };
// struct M_act {
//   using M = _underlying_set_;
//   using X = _data_monoid_::T;
//   static X op(const M &a, const M &b)
//   { return _a_op_b_; }
//   static constexpr X identity()
//   { return _identity_element_; }
//   static X actInto(const M &m, long long n, const X &x)
//   { return _m_act_n_of_x_; }
// };

template<class Monoid, class M_act>
struct LazySegTree {
private:
  using X = typename Monoid::T;
  using M = typename M_act::M;
  int n, h;
  std::vector<X> data;
  std::vector<M> lazy;
  std::vector<int> nodeLeft;
  std::vector<int> nodeLength;
  // call before use data[i]
  void eval(int i) {
    if(lazy[i] == M_act::identity()) return;
    data[i] = M_act::actInto(lazy[i], nodeLeft[i], nodeLength[i], data[i]);
    if(i < n) {
      lazy[i * 2] = M_act::op(lazy[i], lazy[i * 2]);
      lazy[i * 2 + 1] = M_act::op(lazy[i], lazy[i * 2 + 1]);
    }
    lazy[i] = M_act::identity();
  }
  // call before use seg[i] = data[i + n]
  void evalDown(int i) {
    i += n;
    for(int j = h - 1; j >= 0; j--) eval(i >> j);
  }
  // call after touch seg[i] = data[i + n]
  void propUp(int i) {
    i += n;
    while(i >>= 1) eval(i * 2), eval(i * 2 + 1),
      data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);
  }
  int logbin(int x) {
    int h = 0;
    x = x & 0xFFFF0000 ? (h += 16, x) & 0xFFFF0000 : x;
    x = x & 0xFF00FF00 ? (h += 8, x) & 0xFF00FF00 : x;
    x = x & 0xF0F0F0F0 ? (h += 4, x) & 0xF0F0F0F0 : x;
    x = x & 0xCCCCCCCC ? (h += 2, x) & 0xCCCCCCCC : x;
    x = x & 0xAAAAAAAA ? (h += 1, x) & 0xAAAAAAAA : x;
    return h;
  }
public:
  LazySegTree(): n(0) {}
  LazySegTree(int n): n(n) {
    h = logbin(n) + 1;
    data.resize(2 * n, Monoid::identity());
    lazy.resize(2 * n, M_act::identity());
    nodeLeft.resize(2 * n);
    nodeLength.resize(2 * n, 1);
    for(int i = 0; i < n; i++) nodeLeft[i + n] = i;
    for(int i = n - 1; i > 0; i--) // fill from deep
      nodeLeft[i] = min(nodeLeft[i * 2], nodeLeft[i * 2 + 1]),
      nodeLength[i] = nodeLength[i * 2] + nodeLength[i * 2 + 1];

  }
  template <class InputIter, class = typename std::iterator_traits<InputIter>::value_type>
    LazySegTree(InputIter first, InputIter last)
    : LazySegTree(std::distance(first, last)) {
      copy(first, last, std::begin(data) + n);
      for(int i = n - 1; i > 0; i--) // fill from deep
        data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);
    }
  void act(int l, int r, const M &m) {
    evalDown(l);
    evalDown(r - 1);
    int tl = l, tr = r;
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) eval(l), lazy[l] = m, eval(l), l++;
      if(r & 1) --r, eval(r), lazy[r] = m, eval(r);
    }
    propUp(tl);
    propUp(tr - 1);
  }
  void set(int i, const X &x) {
    evalDown(i);
    data[i + n] = x;
    propUp(i);
  }
  X get(int i) {
    evalDown(i);
    return data[i + n];
  }
  X query(int l, int r) {
    evalDown(l);
    evalDown(r - 1);
    X tmpL = Monoid::identity(), tmpR = Monoid::identity();
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) eval(l), tmpL = Monoid::op(tmpL, data[l]), l++;
      if(r & 1) --r, eval(r), tmpR = Monoid::op(data[r], tmpR);
    }
    return Monoid::op(tmpL, tmpR);
  }
  inline void dum(int r = -1) {
#ifdef DEBUG
    std::ostream & o =
#ifdef USE_COUT
      std::cout
#else
      std::cerr
#endif
      ;
    if(r < 0) r = n;
    o << "{";
    for(int i = 0; i < std::min(r, n); i++) o << (i ? ", " : "") << get(i);
    o << "}" << std::endl;
#endif
  }
};

/// }}}--- ///

// TODO : to lib
// // Monoid, M_act expamles {{{
//
// struct RangeMin {
//   using T = long long;
//   static T op(const T& a, const T& b) { return std::min(a, b); }
//   static constexpr T identity() { return std::numeric_limits<T>::max(); }
// };
//
// struct RangeMax {
//   using T = long long;
//   static T op(const T& a, const T& b) { return std::max(a, b); }
//   static constexpr T identity() { return std::numeric_limits<T>::min(); }
// };
//
// struct RangeSum {
//   using T = Int;
//   static T op(const T& a, const T& b) { return a + b; }
//   static constexpr T identity() { return T(); }
// };
//
// // MinAdd m + x
// // MinSet m
// // SumAdd m * n + x
// // SumSet m * n
//
// struct RangeMinAdd {
//   using M = long long;
//   using X = RangeMin::T;
//   static M op(const M &a, const M &b)
//   { return a + b; }
//   static constexpr M identity()
//   { return 0; }
//   static X actInto(const M & m, long long, long long, const X & x)
//   { return m + x; }
// };
//
// struct RangeMinSet {
//   using M = long long;
//   using X = RangeMin::T;
//   static M op(const M &a, const M &)
//   { return a; }
//   static constexpr M identity()
//   { return std::numeric_limits<M>::min(); }
//   static X actInto(const M & m, long long, long long, const X &)
//   { return m; }
// };
//
// struct RangeSumAdd {
//   using M = Int;
//   using X = RangeSum::T;
//   static M op(const M &a, const M &b)
//   { return a + b; }
//   static constexpr M identity()
//   { return 0; }
//   static X actInto(const M & m, long long, long long n, const X & x)
//   { return m * n + x; }
// };
//
// struct RangeSumSet {
//   using M = long long;
//   using X = RangeSum::T;
//   static M op(const M &a, const M &)
//   { return a; }
//   static constexpr M identity()
//   { return std::numeric_limits<M>::min(); }
//   static X actInto(const M & m, long long, long long n, const X &)
//   { return m * n; }
// };
//
// // }}}

// Monoid, M_act expamles {{{

struct RangeMin {
  using T = long long;
  static T op(const T& a, const T& b) { return std::min(a, b); }
  static constexpr T identity() { return std::numeric_limits<T>::max(); }
};

struct RangeMax {
  using T = long long;
  static T op(const T& a, const T& b) { return std::max(a, b); }
  static constexpr T identity() { return std::numeric_limits<T>::min(); }
};

struct RangeSum {
  using T = Int;
  static T op(const T& a, const T& b) { return a + b; }
  static constexpr T identity() { return T(); }
};

// MinAdd m + x
// MinSet m
// SumAdd m * n + x
// SumSet m * n

struct RangeMinAdd {
  using M = long long;
  using X = RangeMin::T;
  static M op(const M &a, const M &b)
  { return a + b; }
  static constexpr M identity()
  { return 0; }
  static X actInto(const M & m, long long, long long, const X & x)
  { return m + x; }
};

struct RangeMinSet {
  using M = long long;
  using X = RangeMin::T;
  static M op(const M &a, const M &)
  { return a; }
  static constexpr M identity()
  { return std::numeric_limits<M>::min(); }
  static X actInto(const M & m, long long, long long, const X &)
  { return m; }
};

struct RangeSumAdd {
  using M = Int;
  using X = RangeSum::T;
  static M op(const M &a, const M &b)
  { return a + b; }
  static constexpr M identity()
  { return 0; }
  static X actInto(const M & m, long long l, long long n, const X & x)
  { return m * getC(l, l + n) + x; }
};

struct RangeSumSet {
  using M = long long;
  using X = RangeSum::T;
  static M op(const M &a, const M &)
  { return a; }
  static constexpr M identity()
  { return std::numeric_limits<M>::min(); }
  static X actInto(const M & m, long long l, long long n, const X &)
  { return m * n; }
};

// }}}


int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n;
  for(int i = 0; i < n; i++) cin >> s[i];
  for(int i = 0; i < n; i++) cin >> c[i];
  HLD hld(n);
  for(int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b; a--; b--;
    hld.addEdge(a, b);
  }
  hld.build();
  vector<Int> sv(n);
  for(int i = 0; i < n; i++) sv[hld[i]] = s[i];
  LazySegTree<RangeSum, RangeSumAdd> qina(begin(sv), end(sv));
  for(int i = 0; i < n; i++) csum[hld[i]] = c[i];
  for(int i = 1; i < n; i++) csum[i] += csum[i-1];
  // vector<Int> ecas(n);
  // for(int i = 0; i < n; i++) ecas[hld[i]] = s[i];
  // for(int i = 1; i < n; i++) ecas[i] = ecas[i] + ecas[i - 1];
  int q;
  cin >> q;
  while(q--) {
    int c;
    cin >> c;
    if(c == 0) { // update
      int s, t, k;
      cin >> s >> t >> k;
      s--; t--;
      int lca = hld.lca(s, t);
      auto f = [&](int l, int r) {
        qina.act(l, r, k);
      };
      hld.query(lca, s, f);
      hld.query(lca, t, f, 0);
    } else { // ask
      int s, t;
      cin >> s >> t;
      s--; t--;
      int lca = hld.lca(s, t);
      Int res = 0;
      auto f = [&](int l, int r) {
        res += qina.query(l, r);
        // res += ecas[r - 1];
        // if(l - 1 >= 0) res -= ecas[l - 1];
      };
      hld.query(lca, s, f);
      hld.query(lca, t, f, 0);
      cout << res << endl;
    }
  }
  return 0;
}
yukicoder

結果

テストケース

ソースコード
