結果
| 問題 | No.650 行列木クエリ |
| ユーザー |
 outline
|
| 提出日時 | 2022-11-08 14:44:26 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,821 bytes |
| コンパイル時間 | 1,986 ms |
| コンパイル使用メモリ | 155,988 KB |
| 最終ジャッジ日時 | 2025-02-08 19:12:35 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 4 WA * 6 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <cmath>#include <queue>#include <string>#include <map>#include <set>#include <stack>#include <tuple>#include <deque>#include <array>#include <numeric>#include <bitset>#include <iomanip>#include <cassert>#include <chrono>#include <random>#include <limits>#include <iterator>#include <functional>#include <sstream>#include <fstream>#include <complex>#include <cstring>#include <unordered_map>#include <unordered_set>#include <memory>using namespace std;// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")// #pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")using ll = long long;constexpr int INF = 1001001001;// constexpr int mod = 1000000007;constexpr int mod = 998244353;template<class T>inline bool chmax(T& x, T y){if(x < y){x = y;return true;}return false;}template<class T>inline bool chmin(T& x, T y){if(x > y){x = y;return true;}return false;}constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};constexpr int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};struct HeavyLightDecomposition {using Graph = vector<vector<int>>;int V;Graph& g;vector<int> subtree_size, head, in, out, par, inverse;HeavyLightDecomposition(Graph& g_) :V(g_.size()), g(g_), subtree_size(V), head(V), in(V), out(V), par(V), inverse(V) {}void calc_subtree_size(int cur, int p){if(g[cur].size() && g[cur][0] == p){swap(g[cur][0], g[cur].back());}subtree_size[cur] = 1;par[cur] = p;for(auto& child : g[cur]){if(child == p) continue;calc_subtree_size(child, cur);subtree_size[cur] += subtree_size[child];if(subtree_size[g[cur][0]] < subtree_size[child]){swap(g[cur][0], child);}}}void dfs(int cur, int p, int& times){in[cur] = times++;inverse[in[cur]] = cur;for(auto& child : g[cur]){if(child == p) continue;head[child] = (g[cur][0] == child ? head[cur] : child);dfs(child, cur, times);}out[cur] = times;}void build(int root = 0){calc_subtree_size(root, -1);int t = 0;dfs(root, -1, t);}int get(int v, int k){for(;;){int u = head[v];if(in[v] - k >= in[u]){ // u, v in same groupreturn inverse[in[v] - k];}k -= in[v] - in[u] + 1;v = par[u];}}int lca(int u, int v){for(;; v = par[head[v]]){if(in[u] > in[v]) swap(u, v);if(head[u] == head[v]) return u;}}// pathvector<pair<int, int>> get_sections(int u, int v, bool is_edge = false){vector<pair<int, int>> res;for(;; v = par[head[v]]){if(in[u] > in[v]) swap(u, v);if(head[u] == head[v]) break;res.emplace_back(in[head[v]], in[v] + 1);}res.emplace_back(in[u] + is_edge, in[v] + 1);return res;}// subtreepair<int, int> get_section(int v, bool is_edge = false){return {in[v] + is_edge, out[v]};}int operator[](const int& v) const {return in[v];}int edge(int u, int v){return in[in[u] > in[v] ? u : v];}};template<typename Monoid>struct SegmentTree{using F = function<Monoid(Monoid, Monoid)>;int sz;vector<Monoid> seg;const F f;const Monoid M1;SegmentTree(const F f, const Monoid& M1) : f(f), M1(M1) {}SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void resize(int n){sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x){seg[k + sz] = x;}void build(){for(int k = sz - 1; k > 0; --k){seg[k] = f(seg[k << 1], seg[k << 1 | 1]);}}void update(int k, const Monoid &x){k += sz;seg[k] = x;while(k >>= 1){seg[k] = f(seg[k << 1], seg[k << 1 | 1]);}}Monoid query(int a, int b){Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[](const int &k) const{return seg[k + sz];}// (type = true) : find_last// (type = false) : find_firsttemplate<typename C>int find_subtree(int a, const C &check, Monoid &M, bool type){while(a < sz){Monoid nxt = type ? f(seg[a << 1 | type], M) : f(M, seg[a << 1 | type]);if(check(nxt)) a = a << 1 | type;else M = nxt, a = 2 * a + 1 - type;}return a - sz;}template<typename C>int find_first(int a, const C &check){Monoid L = M1;if(a <= 0){if(check(f(L, seg[1]))) return find_subtree(1, check, L, false);return -1;}int b = sz;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){if(a & 1){Monoid nxt = f(L, seg[a]);if(check(nxt)) return find_subtree(a, check, L, false);L = nxt;++a;}}return -1;}template<typename C>int find_last(int b, const C &check){Monoid R = M1;if(b >= sz){if(check(f(seg[1], R))) return find_subtree(1, check, R, true);return -1;}int a = sz;for(b += sz; a < b; a >>= 1, b >>= 1){if(b & 1){Monoid nxt = f(seg[--b], R);if(check(nxt)) return find_subtree(b, check, R, true);R = nxt;}}return -1;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vector<int> a(N), b(N);vector<vector<int>> g(N);for(int i = 0; i < N - 1; ++i){cin >> a[i] >> b[i];g[a[i]].emplace_back(b[i]);g[b[i]].emplace_back(a[i]);}HeavyLightDecomposition hld(g);hld.build();using S = array<array<int, 2>, 2>;auto op = [&](S l, S r) -> S {S res = {0, 0,0, 0};for(int k = 0; k < 2; ++k){for(int i = 0; i < 2; ++i){for(int j = 0; j < 2; ++j){res[i][j] += l[i][k] * r[k][j];}}}return res;};S E = {1, 0,0, 1};SegmentTree<S> seg(N, op, E);int Q;cin >> Q;for(int q = 0; q < Q; ++q){char c; cin >> c;if(c == 'x'){int i;cin >> i;S x;for(int i = 0; i < 2; ++i){for(int j = 0; j < 2; ++j){cin >> x[i][j];}}seg.update(hld.edge(a[i], b[i]), x);}else{int i, j;cin >> i >> j;auto sections = hld.get_sections(i, j, true);sort(begin(sections), end(sections));S ans = E;for(auto& [l, r] : sections){ans = op(ans, seg.query(l, r));}cout << ans[0][0] << ' ' << ans[0][1] << ' ';cout << ans[1][0] << ' ' << ans[1][1] << '\n';}}return 0;}