結果

問題 No.2342 Triple Tree Query (Hard)
ユーザー 也吏也吏
提出日時 2024-12-02 16:22:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 907 ms / 10,000 ms
コード長 7,920 bytes
コンパイル時間 4,080 ms
コンパイル使用メモリ 146,708 KB
実行使用メモリ 91,900 KB
最終ジャッジ日時 2024-12-02 16:22:47
合計ジャッジ時間 22,793 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#define NO_FREOPEN
#include <algorithm>
#include <array>
#include <iostream>
#include <queue>
#include <ranges>
#include <vector>
#include <type_traits>
using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;
void set_io(std::string name)
{
#ifndef NO_FREOPEN
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
#endif
std::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 n, m;
std::cin >> 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 == 4) {
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 == 2) {
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];
}
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0