結果
問題 | No.2342 Triple Tree Query (Hard) |
ユーザー |
|
提出日時 | 2024-12-02 16:21:31 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,912 bytes |
コンパイル時間 | 2,066 ms |
コンパイル使用メモリ | 147,952 KB |
実行使用メモリ | 817,664 KB |
最終ジャッジ日時 | 2024-12-02 16:21:45 |
合計ジャッジ時間 | 11,411 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 RE * 1 |
other | WA * 6 RE * 28 MLE * 2 |
ソースコード
#include <algorithm>#include <array>#include <iostream>#include <queue>#include <ranges>#include <type_traits>#include <vector>using i64 = long long;using u32 = unsigned int;using u64 = unsigned long long;void set_io(std::string name){#ifndef NO_FREOPENfreopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);#endifstd::cin.tie(nullptr);std::ios::sync_with_stdio(false);}template <int M> struct static_modint{static constexpr u32 UM = M;static_assert(UM < 0x80'00'00'00u);u32 v;constexpr static_modint() : v(0) {}template <typename T, std::enable_if_t<std::is_signed_v<T>> * = nullptr>constexpr static_modint(T n) : v((n %= M) < 0 ? n + M : n){}template <typename T, std::enable_if_t<std::is_unsigned_v<T>> * = nullptr>constexpr static_modint(T n) : v(n %= UM){}using mint = static_modint;static mint raw(u32 v){mint res;res.v = v;return res;}constexpr u32 val() const { return v; }mint operator-() const { return mint::raw(v == 0 ? 0u : UM - v); }mint &operator+=(mint a){if ((v += a.v) >= UM) v -= UM;return *this;}mint &operator-=(mint a){if ((v += UM - a.v) >= UM) v -= UM;return *this;}mint &operator*=(mint a){v = (u64)v * a.v % UM;return *this;}mint &operator/=(mint a) { return *this *= a.inv(); }friend mint operator+(mint a, mint b) { return a += b; }friend mint operator-(mint a, mint b) { return a -= b; }friend mint operator*(mint a, mint b) { return a *= b; }friend mint operator/(mint a, mint b) { return a /= b; }mint pow(u64 n) const{mint res = 1, base = *this;while (n) {if (n & 1) res *= base;base *= base;n >>= 1;}return res;}mint inv() const { return pow(UM - 2); }};using mint = static_modint<998'244'353>;struct AffineMonoid{mint k, b;AffineMonoid() : k(1), b(0) {}AffineMonoid(mint k, mint b) : k(k), b(b) {}AffineMonoid &operator*=(AffineMonoid x){k *= x.k;b = x.k * b + x.b;return *this;}friend AffineMonoid operator*(AffineMonoid x, AffineMonoid y) { return y *= x; }mint operator()(mint x) const { return k * x + b; }};int ceil_pow2(int x){int y = 0;while ((1 << y) < x) y++;return y;}struct Segtree{int n, log, size;std::vector<AffineMonoid> s;Segtree(int n) : n(n), log(ceil_pow2(n)), size(1 << log), s(size * 2) {}void apply_at(int x, const AffineMonoid &tag){s[x] *= tag;}void push(int p){apply_at(p * 2, s[p]);apply_at(p * 2 + 1, s[p]);s[p] = {};}void apply(int l, int r, const AffineMonoid &tag){l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}while (l < r) {if (l & 1) apply_at(l++, tag);if (r & 1) apply_at(--r, tag);l >>= 1;r >>= 1;}}AffineMonoid get(int x){x += size;for (int i = log; i >= 1; i--) push(x >> i);return s[x];}};constexpr int MAXK = 10;int main(){set_io("tour");int sub, n, m;std::cin >> sub >> n >> m;int n2 = n + MAXK;std::vector<std::vector<int>> adj(n2);for (int i = 1; i < n; i++) {int u, v;std::cin >> u >> v;u--;v--;adj[u].emplace_back(v);adj[v].emplace_back(u);}for (int i = n; i < n2; i++) {if (i == n) {adj[i].emplace_back(0);adj[0].emplace_back(i);} else {adj[i].emplace_back(i - 1);adj[i - 1].emplace_back(i);}}std::vector<mint> a(n);for (int i = 0; i < n; i++) {int x;std::cin >> x;a[i] = x;}std::vector<int> bfs_ord;std::vector<int> fa(n2, -1), dep(n2);{std::queue<int> q;q.emplace(n2 - 1);while (!q.empty()) {auto u = q.front();q.pop();bfs_ord.emplace_back(u);for (auto v : adj[u]) {std::erase(adj[v], u);fa[v] = u;dep[v] = dep[u] + 1;q.emplace(v);}}}std::vector<int> size(n2);for (auto u : bfs_ord | std::views::reverse) {size[u] = 1;for (auto &v : adj[u]) {size[u] += size[v];if (size[v] > size[adj[u][0]]) {std::swap(v, adj[u][0]);}}}std::vector<int> chain_idx(n2);std::vector<int> top(n2);top[n2 - 1] = n2 - 1;for (auto u : bfs_ord) {for (auto v : adj[u]) {if (v == adj[u][0]) chain_idx[v] = chain_idx[u] + 1;else chain_idx[v] = 0;if (chain_idx[v] > MAXK) top[v] = top[u];else top[v] = v;}}std::vector<std::array<std::vector<int>, MAXK + 1>> kadj(n2);for (auto u : bfs_ord | std::views::reverse) {kadj[u][0].emplace_back(u);for (int k = 1; k <= MAXK; k++) {for (auto v : adj[u]) {for (auto w : kadj[v][k - 1]) {kadj[u][k].emplace_back(w);}}}}std::vector<std::array<int, MAXK + 1>> kchain(n2);for (int i = 0; i < n2; i++) {kchain[i].fill(-1);kchain[i][0] = i;for (int k = 1; k <= MAXK; k++) {int pre = kchain[i][k - 1];if (adj[pre].size() == 0) break;kchain[i][k] = adj[pre][0];}}int cnt = 0;std::vector<int> idx(n, -1);std::vector<int> begin1(n), end1(n);auto dfs1 = [&](auto &&self, int u) -> void {if (u < n) begin1[u] = cnt;if (chain_idx[u] >= MAXK && u < n) idx[u] = cnt++;for (auto v : adj[u]) self(self, v);if (u < n) end1[u] = cnt;};dfs1(dfs1, n2 - 1);std::vector<int> begin2(n), end2(n);auto dfs2 = [&](auto &&self, int u) -> void {for (auto v : kadj[u][MAXK]) {if (idx[v] == -1) {idx[v] = cnt++;}}if (u < n) begin2[u] = cnt;for (auto v : adj[u]) self(self, v);if (u < n) end2[u] = cnt;};dfs2(dfs2, n2 - 1);std::vector<std::array<int, MAXK + 1>> begin3(n2), end3(n2);for (int u = 0; u < n2; u++) {for (int k = 0; k <= MAXK; k++) {begin3[u][k] = n2;end3[u][k] = -1;for (auto v : kadj[u][k]) {if (v >= n || chain_idx[v] >= MAXK) continue;begin3[u][k] = std::min(begin3[u][k], idx[v]);end3[u][k] = std::max(end3[u][k], idx[v]);}end3[u][k]++;}}Segtree s(n);auto apply_subtree_distance = [&](int u, int d, const AffineMonoid &affine){if (begin3[u][d] != n2) s.apply(begin3[u][d], end3[u][d], affine);if (kchain[u][d] != -1 && chain_idx[kchain[u][d]] >= MAXK) s.apply(idx[kchain[u][d]], idx[kchain[u][d]] + 1, affine);};for (int i = 0; i < m; i++) {int type;std::cin >> type;if (type == 1) {int x;std::cin >> x;x--;std::cout << s.get(idx[x])(a[x]).val() << "\n";} else if (type == 2) {int u, v, k, b;std::cin >> u >> v >> k >> b;u--;v--;AffineMonoid affine(k, b);while (top[u] != top[v]) {if (dep[top[u]] < dep[top[v]]) std::swap(u, v);s.apply(idx[top[u]], idx[u] + 1, affine);u = fa[top[u]];}if (idx[u] > idx[v]) std::swap(u, v);s.apply(idx[u], idx[v] + 1, affine);} else if (type == 3) {int u, k, b;std::cin >> u >> k >> b;u--;AffineMonoid affine(k, b);s.apply(begin1[u], end1[u], affine);s.apply(begin2[u], end2[u], affine);for (int j = 0; j <= MAXK; j++) {if (begin3[u][j] != n2) {s.apply(begin3[u][j], end3[u][j], affine);}}} else if (type == 4) {int u, r, k, b;std::cin >> u >> r >> k >> b;u--;AffineMonoid affine(k, b);while (r >= 0) {apply_subtree_distance(u, r, affine);if (r - 1 >= 0) apply_subtree_distance(u, r - 1, affine);r--;u = fa[u];}}}}