結果
| 問題 | No.2341 Triple Tree Query (Medium) |
| ユーザー |
 suisen
|
| 提出日時 | 2023-06-02 23:45:20 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 263 ms / 5,000 ms |
| コード長 | 32,819 bytes |
| コンパイル時間 | 4,182 ms |
| コンパイル使用メモリ | 329,560 KB |
| 実行使用メモリ | 32,888 KB |
| 最終ジャッジ日時 | 2023-08-28 06:29:35 |
| 合計ジャッジ時間 | 15,419 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 2 ms
4,376 KB |
| testcase_02 | AC | 260 ms
17,696 KB |
| testcase_03 | AC | 261 ms
17,592 KB |
| testcase_04 | AC | 256 ms
17,688 KB |
| testcase_05 | AC | 261 ms
17,548 KB |
| testcase_06 | AC | 263 ms
17,724 KB |
| testcase_07 | AC | 208 ms
29,512 KB |
| testcase_08 | AC | 215 ms
27,980 KB |
| testcase_09 | AC | 207 ms
32,888 KB |
| testcase_10 | AC | 209 ms
29,876 KB |
| testcase_11 | AC | 211 ms
31,736 KB |
| testcase_12 | AC | 214 ms
27,404 KB |
| testcase_13 | AC | 214 ms
29,268 KB |
| testcase_14 | AC | 207 ms
28,388 KB |
| testcase_15 | AC | 214 ms
31,852 KB |
| testcase_16 | AC | 219 ms
26,140 KB |
| testcase_17 | AC | 162 ms
18,400 KB |
| testcase_18 | AC | 167 ms
18,364 KB |
| testcase_19 | AC | 166 ms
18,456 KB |
| testcase_20 | AC | 158 ms
18,300 KB |
| testcase_21 | AC | 161 ms
18,408 KB |
| testcase_22 | AC | 159 ms
18,364 KB |
| testcase_23 | AC | 157 ms
18,236 KB |
| testcase_24 | AC | 157 ms
18,264 KB |
| testcase_25 | AC | 249 ms
17,772 KB |
| testcase_26 | AC | 252 ms
17,716 KB |
| testcase_27 | AC | 254 ms
17,780 KB |
| testcase_28 | AC | 249 ms
18,104 KB |
| testcase_29 | AC | 253 ms
17,732 KB |
| testcase_30 | AC | 184 ms
18,348 KB |
| testcase_31 | AC | 181 ms
18,364 KB |
| testcase_32 | AC | 184 ms
18,264 KB |
| testcase_33 | AC | 254 ms
18,228 KB |
| testcase_34 | AC | 256 ms
18,144 KB |
| testcase_35 | AC | 249 ms
17,956 KB |
| testcase_36 | AC | 250 ms
18,220 KB |
| testcase_37 | AC | 251 ms
18,068 KB |
ソースコード
#include <bits/stdc++.h>
#ifdef _MSC_VER
# include <intrin.h>
#else
# include <x86intrin.h>
#endif
#include <limits>
#include <type_traits>
namespace suisen {
// ! utility
template <typename ...Types>
using constraints_t = std::enable_if_t<std::conjunction_v<Types...>, std::nullptr_t>;
template <bool cond_v, typename Then, typename OrElse>
constexpr decltype(auto) constexpr_if(Then&& then, OrElse&& or_else) {
if constexpr (cond_v) {
return std::forward<Then>(then);
} else {
return std::forward<OrElse>(or_else);
}
}
// ! function
template <typename ReturnType, typename Callable, typename ...Args>
using is_same_as_invoke_result = std::is_same<std::invoke_result_t<Callable, Args...>, ReturnType>;
template <typename F, typename T>
using is_uni_op = is_same_as_invoke_result<T, F, T>;
template <typename F, typename T>
using is_bin_op = is_same_as_invoke_result<T, F, T, T>;
template <typename Comparator, typename T>
using is_comparator = std::is_same<std::invoke_result_t<Comparator, T, T>, bool>;
// ! integral
template <typename T, typename = constraints_t<std::is_integral<T>>>
constexpr int bit_num = std::numeric_limits<std::make_unsigned_t<T>>::digits;
template <typename T, unsigned int n>
struct is_nbit { static constexpr bool value = bit_num<T> == n; };
template <typename T, unsigned int n>
static constexpr bool is_nbit_v = is_nbit<T, n>::value;
// ?
template <typename T>
struct safely_multipliable {};
template <>
struct safely_multipliable<int> { using type = long long; };
template <>
struct safely_multipliable<long long> { using type = __int128_t; };
template <>
struct safely_multipliable<unsigned int> { using type = unsigned long long; };
template <>
struct safely_multipliable<unsigned long int> { using type = __uint128_t; };
template <>
struct safely_multipliable<unsigned long long> { using type = __uint128_t; };
template <>
struct safely_multipliable<float> { using type = float; };
template <>
struct safely_multipliable<double> { using type = double; };
template <>
struct safely_multipliable<long double> { using type = long double; };
template <typename T>
using safely_multipliable_t = typename safely_multipliable<T>::type;
template <typename T, typename = void>
struct rec_value_type {
using type = T;
};
template <typename T>
struct rec_value_type<T, std::void_t<typename T::value_type>> {
using type = typename rec_value_type<typename T::value_type>::type;
};
template <typename T>
using rec_value_type_t = typename rec_value_type<T>::type;
} // namespace suisen
// ! type aliases
using i128 = __int128_t;
using u128 = __uint128_t;
template <typename T>
using pq_greater = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// ! macros (internal)
#define DETAIL_OVERLOAD2(_1,_2,name,...) name
#define DETAIL_OVERLOAD3(_1,_2,_3,name,...) name
#define DETAIL_OVERLOAD4(_1,_2,_3,_4,name,...) name
#define DETAIL_REP4(i,l,r,s) for(std::remove_reference_t<std::remove_const_t<decltype(r)>>i=(l);i<(r);i+=(s))
#define DETAIL_REP3(i,l,r) DETAIL_REP4(i,l,r,1)
#define DETAIL_REP2(i,n) DETAIL_REP3(i,0,n)
#define DETAIL_REPINF3(i,l,s) for(std::remove_reference_t<std::remove_const_t<decltype(l)>>i=(l);;i+=(s))
#define DETAIL_REPINF2(i,l) DETAIL_REPINF3(i,l,1)
#define DETAIL_REPINF1(i) DETAIL_REPINF2(i,0)
#define DETAIL_RREP4(i,l,r,s) for(std::remove_reference_t<std::remove_const_t<decltype(r)>>i=(l)+fld((r)-(l)-1,s)*(s);i>=(l);i-=(s))
#define DETAIL_RREP3(i,l,r) DETAIL_RREP4(i,l,r,1)
#define DETAIL_RREP2(i,n) DETAIL_RREP3(i,0,n)
#define DETAIL_CAT_I(a, b) a##b
#define DETAIL_CAT(a, b) DETAIL_CAT_I(a, b)
#define DETAIL_UNIQVAR(tag) DETAIL_CAT(tag, __LINE__)
// ! macros
#define REP(...) DETAIL_OVERLOAD4(__VA_ARGS__, DETAIL_REP4 , DETAIL_REP3 , DETAIL_REP2 )(__VA_ARGS__)
#define RREP(...) DETAIL_OVERLOAD4(__VA_ARGS__, DETAIL_RREP4 , DETAIL_RREP3 , DETAIL_RREP2 )(__VA_ARGS__)
#define REPINF(...) DETAIL_OVERLOAD3(__VA_ARGS__, DETAIL_REPINF3, DETAIL_REPINF2, DETAIL_REPINF1)(__VA_ARGS__)
#define LOOP(n) for (std::remove_reference_t<std::remove_const_t<decltype(n)>> DETAIL_UNIQVAR(loop_variable) = n; DETAIL_UNIQVAR(loop_variable) --> 0;)
#define ALL(iterable) std::begin(iterable), std::end(iterable)
#define INPUT(type, ...) type __VA_ARGS__; read(__VA_ARGS__)
// ! debug
#ifdef LOCAL
# define debug(...) debug_internal(#__VA_ARGS__, __VA_ARGS__)
template <class T, class... Args>
void debug_internal(const char* s, T&& first, Args&&... args) {
constexpr const char* prefix = "[\033[32mDEBUG\033[m] ";
constexpr const char* open_brakets = sizeof...(args) == 0 ? "" : "(";
constexpr const char* close_brakets = sizeof...(args) == 0 ? "" : ")";
std::cerr << prefix << open_brakets << s << close_brakets << ": " << open_brakets << std::forward<T>(first);
((std::cerr << ", " << std::forward<Args>(args)), ...);
std::cerr << close_brakets << "\n";
}
#else
# define debug(...) void(0)
#endif
// ! I/O utilities
// __int128_t
std::ostream& operator<<(std::ostream& dest, __int128_t value) {
std::ostream::sentry s(dest);
if (s) {
__uint128_t tmp = value < 0 ? -value : value;
char buffer[128];
char* d = std::end(buffer);
do {
--d;
*d = "0123456789"[tmp % 10];
tmp /= 10;
} while (tmp != 0);
if (value < 0) {
--d;
*d = '-';
}
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
// __uint128_t
std::ostream& operator<<(std::ostream& dest, __uint128_t value) {
std::ostream::sentry s(dest);
if (s) {
char buffer[128];
char* d = std::end(buffer);
do {
--d;
*d = "0123456789"[value % 10];
value /= 10;
} while (value != 0);
int len = std::end(buffer) - d;
if (dest.rdbuf()->sputn(d, len) != len) {
dest.setstate(std::ios_base::badbit);
}
}
return dest;
}
// pair
template <typename T, typename U>
std::ostream& operator<<(std::ostream& out, const std::pair<T, U>& a) {
return out << a.first << ' ' << a.second;
}
// tuple
template <unsigned int N = 0, typename ...Args>
std::ostream& operator<<(std::ostream& out, const std::tuple<Args...>& a) {
if constexpr (N >= std::tuple_size_v<std::tuple<Args...>>) return out;
else {
out << std::get<N>(a);
if constexpr (N + 1 < std::tuple_size_v<std::tuple<Args...>>) out << ' ';
return operator<<<N + 1>(out, a);
}
}
// vector
template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& a) {
for (auto it = a.begin(); it != a.end();) {
out << *it;
if (++it != a.end()) out << ' ';
}
return out;
}
// array
template <typename T, size_t N>
std::ostream& operator<<(std::ostream& out, const std::array<T, N>& a) {
for (auto it = a.begin(); it != a.end();) {
out << *it;
if (++it != a.end()) out << ' ';
}
return out;
}
inline void print() { std::cout << '\n'; }
template <typename Head, typename... Tail>
inline void print(const Head& head, const Tail &...tails) {
std::cout << head;
if (sizeof...(tails)) std::cout << ' ';
print(tails...);
}
template <typename Iterable>
auto print_all(const Iterable& v, std::string sep = " ", std::string end = "\n") -> decltype(std::cout << *v.begin(), void()) {
for (auto it = v.begin(); it != v.end();) {
std::cout << *it;
if (++it != v.end()) std::cout << sep;
}
std::cout << end;
}
__int128_t stoi128(const std::string& s) {
__int128_t ret = 0;
for (int i = 0; i < int(s.size()); i++) if ('0' <= s[i] and s[i] <= '9') ret = 10 * ret + s[i] - '0';
if (s[0] == '-') ret = -ret;
return ret;
}
__uint128_t stou128(const std::string& s) {
__uint128_t ret = 0;
for (int i = 0; i < int(s.size()); i++) if ('0' <= s[i] and s[i] <= '9') ret = 10 * ret + s[i] - '0';
return ret;
}
// __int128_t
std::istream& operator>>(std::istream& in, __int128_t& v) {
std::string s;
in >> s;
v = stoi128(s);
return in;
}
// __uint128_t
std::istream& operator>>(std::istream& in, __uint128_t& v) {
std::string s;
in >> s;
v = stou128(s);
return in;
}
// pair
template <typename T, typename U>
std::istream& operator>>(std::istream& in, std::pair<T, U>& a) {
return in >> a.first >> a.second;
}
// tuple
template <unsigned int N = 0, typename ...Args>
std::istream& operator>>(std::istream& in, std::tuple<Args...>& a) {
if constexpr (N >= std::tuple_size_v<std::tuple<Args...>>) return in;
else return operator>><N + 1>(in >> std::get<N>(a), a);
}
// vector
template <typename T>
std::istream& operator>>(std::istream& in, std::vector<T>& a) {
for (auto it = a.begin(); it != a.end(); ++it) in >> *it;
return in;
}
// array
template <typename T, size_t N>
std::istream& operator>>(std::istream& in, std::array<T, N>& a) {
for (auto it = a.begin(); it != a.end(); ++it) in >> *it;
return in;
}
template <typename ...Args>
void read(Args &...args) {
(std::cin >> ... >> args);
}
// ! integral utilities
// Returns pow(-1, n)
template <typename T> constexpr inline int pow_m1(T n) {
return -(n & 1) | 1;
}
// Returns pow(-1, n)
template <> constexpr inline int pow_m1<bool>(bool n) {
return -int(n) | 1;
}
// Returns floor(x / y)
template <typename T> constexpr inline T fld(const T x, const T y) {
return (x ^ y) >= 0 ? x / y : (x - (y + pow_m1(y >= 0))) / y;
}
template <typename T> constexpr inline T cld(const T x, const T y) {
return (x ^ y) <= 0 ? x / y : (x + (y + pow_m1(y >= 0))) / y;
}
template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
__attribute__((target("popcnt"))) constexpr inline int popcount(const T x) { return _mm_popcnt_u32(x); }
template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
__attribute__((target("popcnt"))) constexpr inline int popcount(const T x) { return _mm_popcnt_u64(x); }
template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
constexpr inline int count_lz(const T x) { return x ? __builtin_clz(x) : suisen::bit_num<T>; }
template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
constexpr inline int count_lz(const T x) { return x ? __builtin_clzll(x) : suisen::bit_num<T>; }
template <typename T, std::enable_if_t<std::negation_v<suisen::is_nbit<T, 64>>, std::nullptr_t> = nullptr>
constexpr inline int count_tz(const T x) { return x ? __builtin_ctz(x) : suisen::bit_num<T>; }
template <typename T, std::enable_if_t<suisen::is_nbit_v<T, 64>, std::nullptr_t> = nullptr>
constexpr inline int count_tz(const T x) { return x ? __builtin_ctzll(x) : suisen::bit_num<T>; }
template <typename T> constexpr inline int floor_log2(const T x) { return suisen::bit_num<T> - 1 - count_lz(x); }
template <typename T> constexpr inline int ceil_log2(const T x) { return floor_log2(x) + ((x & -x) != x); }
template <typename T> constexpr inline int kth_bit(const T x, const unsigned int k) { return (x >> k) & 1; }
template <typename T> constexpr inline int parity(const T x) { return popcount(x) & 1; }
// ! container
template <typename T, typename Comparator>
auto priqueue_comp(const Comparator comparator) {
return std::priority_queue<T, std::vector<T>, Comparator>(comparator);
}
template <typename Container>
void sort_unique_erase(Container& a) {
std::sort(a.begin(), a.end());
a.erase(std::unique(a.begin(), a.end()), a.end());
}
template <typename InputIterator, typename BiConsumer>
auto foreach_adjacent_values(InputIterator first, InputIterator last, BiConsumer f) -> decltype(f(*first++, *last), void()) {
if (first != last) for (auto itr = first, itl = itr++; itr != last; itl = itr++) f(*itl, *itr);
}
template <typename Container, typename BiConsumer>
auto foreach_adjacent_values(Container &&c, BiConsumer f) -> decltype(c.begin(), c.end(), void()) {
foreach_adjacent_values(c.begin(), c.end(), f);
}
// ! other utilities
// x <- min(x, y). returns true iff `x` has chenged.
template <typename T>
inline bool chmin(T& x, const T& y) {
return y >= x ? false : (x = y, true);
}
// x <- max(x, y). returns true iff `x` has chenged.
template <typename T>
inline bool chmax(T& x, const T& y) {
return y <= x ? false : (x = y, true);
}
template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::string bin(T val, int bit_num = -1) {
std::string res;
if (bit_num != -1) {
for (int bit = bit_num; bit-- > 0;) res += '0' + ((val >> bit) & 1);
} else {
for (; val; val >>= 1) res += '0' + (val & 1);
std::reverse(res.begin(), res.end());
}
return res;
}
template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::vector<T> digits_low_to_high(T val, T base = 10) {
std::vector<T> res;
for (; val; val /= base) res.push_back(val % base);
if (res.empty()) res.push_back(T{ 0 });
return res;
}
template <typename T, std::enable_if_t<std::is_integral_v<T>, std::nullptr_t> = nullptr>
std::vector<T> digits_high_to_low(T val, T base = 10) {
auto res = digits_low_to_high(val, base);
std::reverse(res.begin(), res.end());
return res;
}
template <typename T>
std::string join(const std::vector<T>& v, const std::string& sep, const std::string& end) {
std::ostringstream ss;
for (auto it = v.begin(); it != v.end();) {
ss << *it;
if (++it != v.end()) ss << sep;
}
ss << end;
return ss.str();
}
template <typename Func, typename Seq>
auto transform_to_vector(const Func &f, const Seq &s) {
std::vector<std::invoke_result_t<Func, typename Seq::value_type>> v;
v.reserve(std::size(s)), std::transform(std::begin(s), std::end(s), std::back_inserter(v), f);
return v;
}
template <typename T, typename Seq>
auto copy_to_vector(const Seq &s) {
std::vector<T> v;
v.reserve(std::size(s)), std::copy(std::begin(s), std::end(s), std::back_inserter(v));
return v;
}
template <typename Seq>
Seq concat(Seq s, const Seq &t) {
s.reserve(std::size(s) + std::size(t));
std::copy(std::begin(t), std::end(t), std::back_inserter(s));
return s;
}
template <typename Seq>
std::vector<Seq> split(const Seq s, typename Seq::value_type delim) {
std::vector<Seq> res;
for (auto itl = std::begin(s), itr = itl;; itl = ++itr) {
while (itr != std::end(s) and *itr != delim) ++itr;
res.emplace_back(itl, itr);
if (itr == std::end(s)) return res;
}
}
int digit_to_int(char c) { return c - '0'; }
int lowercase_to_int(char c) { return c - 'a'; }
int uppercase_to_int(char c) { return c - 'A'; }
std::vector<int> digit_str_to_ints(const std::string &s) {
return transform_to_vector(digit_to_int, s);
}
std::vector<int> lowercase_str_to_ints(const std::string &s) {
return transform_to_vector(lowercase_to_int, s);
}
std::vector<int> uppercase_str_to_ints(const std::string &s) {
return transform_to_vector(uppercase_to_int, s);
}
const std::string Yes = "Yes", No = "No", YES = "YES", NO = "NO";
namespace suisen {}
using namespace suisen;
using namespace std;
struct io_setup {
io_setup(int precision = 20) {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(precision);
}
} io_setup_ {};
// ! code from here
#include <atcoder/modint>
using mint = atcoder::modint998244353;
namespace atcoder {
std::istream& operator>>(std::istream& in, mint& a) {
long long e; in >> e; a = e;
return in;
}
std::ostream& operator<<(std::ostream& out, const mint& a) {
out << a.val();
return out;
}
} // namespace atcoder
#include <iostream>
#include <utility>
namespace suisen {
template <typename T>
struct Affine {
T a, b;
Affine(const T &a = 1, const T &b = 0) : a(a), b(b) {}
static Affine<T> id() { return Affine<T>{}; }
static Affine<T> compose(const Affine<T>& f, const Affine<T>& g) { return f.compose(g); }
Affine<T> compose(const Affine<T>& g) const { return { a * g.a, affine(g.b) }; }
template <typename U = T>
U affine(const T &x) const { return U(a) * x + b; }
T operator()(const T &x) const { return affine<T>(x); }
Affine<T> operator+() const { return *this; }
Affine<T> operator-() const { return { -a, -b }; }
Affine<T>& operator++() { ++b; return *this; }
Affine<T>& operator--() { --b; return *this; }
Affine<T> operator++(int) { Affine<T> f(*this); ++(*this); return f; }
Affine<T> operator--(int) { Affine<T> f(*this); --(*this); return f; }
Affine<T>& operator+=(const T& c) { b += c; return *this; }
Affine<T>& operator-=(const T& c) { b -= c; return *this; }
friend Affine<T> operator+(Affine<T> f, const T &c) { f += c; return f; }
friend Affine<T> operator-(Affine<T> f, const T &c) { f -= c; return f; }
Affine<T>& operator+=(const Affine<T> &g) { a += g.a, b += g.b; return *this; }
Affine<T>& operator-=(const Affine<T> &g) { a -= g.a, b -= g.b; return *this; }
friend Affine<T> operator+(Affine<T> f, const Affine<T> &g) { f += g; return f; }
friend Affine<T> operator-(Affine<T> f, const Affine<T> &g) { f -= g; return f; }
friend bool operator==(const Affine<T> &f, const Affine<T> &g) { return f.a == g.a and f.b == g.b; }
friend bool operator!=(const Affine<T> &f, const Affine<T> &g) { return not (f == g); }
friend bool operator< (const Affine<T> &f, const Affine<T> &g) { return f.a < g.a or (f.a == g.a and f.b < g.b); }
friend bool operator<=(const Affine<T> &f, const Affine<T> &g) { return not (g < f); }
friend bool operator> (const Affine<T> &f, const Affine<T> &g) { return g < f; }
friend bool operator>=(const Affine<T> &f, const Affine<T> &g) { return not (f < g); }
template <typename U = T, typename V = T>
operator std::pair<U, V>() { return std::pair<U, V>{ a, b }; }
template <typename U = T, typename V = T>
operator std::tuple<U, V>() { return std::tuple<U, V>{ a, b }; }
friend std::istream& operator<<(std::istream& in, Affine<T> &f) { return in >> f.a >> f.b; }
friend std::ostream& operator>>(std::ostream& out, const Affine<T> &f) { return out << f.a << ' ' << f.b; }
};
} // namespace suisen
#include <cassert>
#include <vector>
namespace suisen {
template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
struct CommutativeDualSegmentTree {
CommutativeDualSegmentTree() {}
CommutativeDualSegmentTree(std::vector<T>&& a) : n(a.size()), m(ceil_pow2(a.size())), data(std::move(a)), lazy(m, id()) {}
CommutativeDualSegmentTree(const std::vector<T>& a) : CommutativeDualSegmentTree(std::vector<T>(a)) {}
CommutativeDualSegmentTree(int n, const T& fill_value) : CommutativeDualSegmentTree(std::vector<T>(n, fill_value)) {}
T operator[](int i) const {
assert(0 <= i and i < n);
T res = data[i];
for (i = (i + m) >> 1; i; i >>= 1) res = mapping(lazy[i], res);
return res;
}
T get(int i) const {
return (*this)[i];
}
void apply(int l, int r, const F& f) {
assert(0 <= l and r <= n);
for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
if (l & 1) apply(l++, f);
if (r & 1) apply(--r, f);
}
}
protected:
int n, m;
std::vector<T> data;
std::vector<F> lazy;
void apply(int k, const F& f) {
if (k < m) {
lazy[k] = composition(f, lazy[k]);
} else if (k - m < n) {
data[k - m] = mapping(f, data[k - m]);
}
}
private:
static int ceil_pow2(int n) {
int m = 1;
while (m < n) m <<= 1;
return m;
}
};
} // namespace suisen
namespace suisen {
template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
struct DualSegmentTree : public CommutativeDualSegmentTree<T, F, mapping, composition, id> {
using base_type = CommutativeDualSegmentTree<T, F, mapping, composition, id>;
using base_type::base_type;
void apply(int l, int r, const F& f) {
push(l, r);
base_type::apply(l, r, f);
}
private:
void push(int k) {
base_type::apply(2 * k, this->lazy[k]), base_type::apply(2 * k + 1, this->lazy[k]);
this->lazy[k] = id();
}
void push(int l, int r) {
const int log = __builtin_ctz(this->m);
l += this->m, r += this->m;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
}
};
template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
DualSegmentTree(int, T)->DualSegmentTree<T, F, mapping, composition, id>;
template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()>
DualSegmentTree(std::vector<T>)->DualSegmentTree<T, F, mapping, composition, id>;
} // namespace suisen
using S = mint;
using F = Affine<mint>;
S mapping(F f, S x) {
return f(x);
}
F composition(F f, F g) {
return Affine<mint>::compose(f, g);
}
F id() {
return Affine<mint>::id();
}
namespace suisen {
class HeavyLightDecomposition {
public:
template <typename Q>
using is_point_update_query = std::is_invocable<Q, int>;
template <typename Q>
using is_range_update_query = std::is_invocable<Q, int, int>;
template <typename Q, typename T>
using is_point_get_query = std::is_same<std::invoke_result_t<Q, int>, T>;
template <typename Q, typename T>
using is_range_fold_query = std::is_same<std::invoke_result_t<Q, int, int>, T>;
using Graph = std::vector<std::vector<int>>;
HeavyLightDecomposition() = default;
HeavyLightDecomposition(Graph &g) : n(g.size()), visit(n), leave(n), head(n), ord(n), siz(n), par(n, -1), dep(n, 0) {
for (int i = 0; i < n; ++i) if (par[i] < 0) dfs(g, i, -1);
int time = 0;
for (int i = 0; i < n; ++i) if (par[i] < 0) hld(g, i, -1, time);
}
int size() const {
return n;
}
int lca(int u, int v) const {
for (;; v = par[head[v]]) {
if (visit[u] > visit[v]) std::swap(u, v);
if (head[u] == head[v]) return u;
}
}
int la(int u, int k, int default_value = -1) const {
if (k < 0) return default_value;
while (u >= 0) {
int h = head[u];
if (visit[u] - k >= visit[h]) return ord[visit[u] - k];
k -= visit[u] - visit[h] + 1;
u = par[h];
}
return default_value;
}
int jump(int u, int v, int d, int default_value = -1) const {
if (d < 0) return default_value;
const int w = lca(u, v);
int uw = dep[u] - dep[w];
if (d <= uw) return la(u, d);
int vw = dep[v] - dep[w];
return d <= uw + vw ? la(v, (uw + vw) - d) : default_value;
}
int dist(int u, int v) const {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
template <typename T, typename Q, typename F, constraints_t<is_range_fold_query<Q, T>, is_bin_op<F, T>> = nullptr>
T fold_path(int u, int v, T identity, F bin_op, Q fold_query, bool is_edge_query = false) const {
T res = identity;
for (;; v = par[head[v]]) {
if (visit[u] > visit[v]) std::swap(u, v);
if (head[u] == head[v]) break;
res = bin_op(fold_query(visit[head[v]], visit[v] + 1), res);
}
return bin_op(fold_query(visit[u] + is_edge_query, visit[v] + 1), res);
}
template <
typename T, typename Q1, typename Q2, typename F,
constraints_t<is_range_fold_query<Q1, T>, is_range_fold_query<Q2, T>, is_bin_op<F, T>> = nullptr
>
T fold_path_noncommutative(int u, int v, T identity, F bin_op, Q1 fold_query, Q2 fold_query_rev, bool is_edge_query = false) const {
T res_u = identity, res_v = identity;
// a := lca(u, v)
// res = fold(u -> a) + fold(a -> v)
while (head[u] != head[v]) {
if (visit[u] < visit[v]) { // a -> v
res_v = bin_op(fold_query(visit[head[v]], visit[v] + 1), res_v);
v = par[head[v]];
} else { // u -> a
res_u = bin_op(res_u, fold_query_rev(visit[head[u]], visit[u] + 1));
u = par[head[u]];
}
}
if (visit[u] < visit[v]) { // a = u
res_v = bin_op(fold_query(visit[u] + is_edge_query, visit[v] + 1), res_v);
} else { // a = v
res_u = bin_op(res_u, fold_query_rev(visit[v] + is_edge_query, visit[u] + 1));
}
return bin_op(res_u, res_v);
}
template <typename Q, constraints_t<is_range_update_query<Q>> = nullptr>
void update_path(int u, int v, Q update_query, bool is_edge_query = false) const {
for (;; v = par[head[v]]) {
if (visit[u] > visit[v]) std::swap(u, v);
if (head[u] == head[v]) break;
update_query(visit[head[v]], visit[v] + 1);
}
update_query(visit[u] + is_edge_query, visit[v] + 1);
}
template <typename T, typename Q, constraints_t<is_range_fold_query<Q, T>> = nullptr>
T fold_subtree(int u, Q fold_query, bool is_edge_query = false) const {
return fold_query(visit[u] + is_edge_query, leave[u]);
}
template <typename Q, constraints_t<is_range_update_query<Q>> = nullptr>
void update_subtree(int u, Q update_query, bool is_edge_query = false) const {
update_query(visit[u] + is_edge_query, leave[u]);
}
template <typename T, typename Q, constraints_t<is_point_get_query<Q, T>> = nullptr>
T get_point(int u, Q get_query) const {
return get_query(visit[u]);
}
template <typename Q, constraints_t<is_point_update_query<Q>> = nullptr>
void update_point(int u, Q update_query) const {
update_query(visit[u]);
}
std::vector<int> inv_ids() const {
std::vector<int> inv(n);
for (int i = 0; i < n; ++i) inv[visit[i]] = i;
return inv;
}
int get_visit_time(int u) const {
return visit[u];
}
int get_leave_time(int u) const {
return leave[u];
}
int get_head(int u) const {
return head[u];
}
int get_kth_visited(int k) const {
return ord[k];
}
int get_subtree_size(int u) const {
return siz[u];
}
int get_parent(int u) const {
return par[u];
}
int get_depth(int u) const {
return dep[u];
}
std::vector<int> get_roots() const {
std::vector<int> res;
for (int i = 0; i < n; ++i) if (par[i] < 0) res.push_back(i);
return res;
}
private:
int n;
std::vector<int> visit, leave, head, ord, siz, par, dep;
int dfs(Graph &g, int u, int p) {
par[u] = p;
siz[u] = 1;
int max_size = 0;
for (int &v : g[u]) {
if (v == p) continue;
dep[v] = dep[u] + 1;
siz[u] += dfs(g, v, u);
if (max_size < siz[v]) {
max_size = siz[v];
std::swap(g[u].front(), v);
}
}
return siz[u];
}
void hld(Graph &g, int u, int p, int &time) {
visit[u] = time, ord[time] = u, ++time;
head[u] = p >= 0 and g[p].front() == u ? head[p] : u;
for (int v : g[u]) {
if (v != p) hld(g, v, u, time);
}
leave[u] = time;
}
};
} // namespace suisen
int main() {
int n, q;
read(n, q);
vector<vector<int>> g(n);
LOOP(n - 1) {
int u, v;
read(u, v);
--u, --v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<mint> x(n);
read(x);
vector<int> par(n, -1);
{
auto dfs = [&](auto dfs, int u) -> void {
for (int v : g[u]) {
par[v] = u;
g[v].erase(find(ALL(g[v]), u));
dfs(dfs, v);
}
};
dfs(dfs, 0);
}
HeavyLightDecomposition hld(g);
vector<int> inv_ids = hld.inv_ids();
// REP(i, n) {
// sort(ALL(g[i]), [&](int u, int v) { return inv_ids[u] < inv_ids[v]; });
// }
const int B = ::sqrt(n);
auto is_large = [&](int i) {
return int(g[i].size()) >= B;
};
vector<int> idx(n);
vector<int> vs1, vs2;
vector<int8_t> mark(n, false);
vector<int> from(n, -1);
{
int num = 0;
REP(i, n) if (is_large(i)) {
from[i] = num;
for (int j : g[i]) {
mark[j] = true;
idx[j] = vs1.size();
vs1.push_back(j);
}
num += g[i].size();
}
}
vector<int> mark_cnt(n);
vector<int> mark_vs;
vector<int> ll(n), lr(n), sl(n), sr(n);
vector<int> lvs;
{
auto dfs = [&](auto dfs, int u) -> void {
mark_cnt[u] = mark_vs.size();
ll[u] = lvs.size();
sl[u] = vs2.size();
if (not mark[u]) {
idx[u] = vs2.size();
vs2.push_back(u);
} else {
mark_vs.push_back(u);
}
if (is_large(u)) {
lvs.push_back(u);
}
for (int v : g[u]) dfs(dfs, v);
lr[u] = lvs.size();
sr[u] = vs2.size();
};
dfs(dfs, 0);
}
vector<mint> d1, d2;
for (int v : vs1) d1.push_back(x[v]);
for (int v : vs2) d2.push_back(x[v]);
DualSegmentTree<mint, F, mapping, composition, id> seg1(d1), seg2(d2);
LOOP(q) {
int qt;
read(qt);
if (qt == 1) {
int v;
read(v);
--v;
if (mark[v]) {
print(seg1.get(idx[v]));
} else {
print(seg2.get(idx[v]));
}
} else if (qt == 2) {
int v, k;
mint c, d;
read(v, k, c, d);
--v;
for (int x : { par[v], v }) if (x != -1) {
if (mark[x]) {
seg1.apply(idx[x], idx[x] + 1, { c, d });
} else {
seg2.apply(idx[x], idx[x] + 1, { c, d });
}
}
if (is_large(v)) {
seg1.apply(from[v], from[v] + int(g[v].size()), { c, d });
} else {
for (int x : g[v]) {
seg2.apply(idx[x], idx[x] + 1, { c, d });
}
}
} else if (qt == 3) {
int v;
mint c, d;
read(v, c, d);
--v;
seg2.apply(sl[v], sr[v], { c, d });
REP(i, ll[v], lr[v]) {
int x = lvs[i];
seg1.apply(from[x], from[x] + int(g[x].size()), { c, d });
}
if (mark[v]) {
seg1.apply(idx[v], idx[v] + 1, { c, d });
}
} else {
int u, v;
mint c, d;
read(u, v, c, d);
--u, --v;
hld.update_path(u, v, [&](int l, int r) {
int off_l = mark_cnt[hld.get_kth_visited(l)];
int off_r = r == n ? mark_vs.size() : mark_cnt[hld.get_kth_visited(r)];
REP(i, off_l, off_r) {
int x = mark_vs[i];
seg1.apply(idx[x], idx[x] + 1, { c, d });
}
seg2.apply(l - off_l, r - off_r, { c, d });
});
}
}
return 0;
}