#include using namespace std; #line 2 "math/isqrt.hpp" #include using namespace std; // floor(sqrt(n)) を返す (ただし n が負の場合は 0 を返す) long long isqrt(long long n) { if (n <= 0) return 0; long long x = sqrt(n); while ((x + 1) * (x + 1) <= n) x++; while (x * x > n) x--; return x; } #line 2 "tree/euler-tour.hpp" #line 2 "graph/graph-template.hpp" template struct edge { int src, to; T cost; edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {} edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {} edge &operator=(const int &x) { to = x; return *this; } operator int() const { return to; } }; template using Edges = vector>; template using WeightedGraph = vector>; using UnweightedGraph = vector>; // Input of (Unweighted) Graph UnweightedGraph graph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { UnweightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; if (is_1origin) x--, y--; g[x].push_back(y); if (!is_directed) g[y].push_back(x); } return g; } // Input of Weighted Graph template WeightedGraph wgraph(int N, int M = -1, bool is_directed = false, bool is_1origin = true) { WeightedGraph g(N); if (M == -1) M = N - 1; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; cin >> c; if (is_1origin) x--, y--; g[x].emplace_back(x, y, c); if (!is_directed) g[y].emplace_back(y, x, c); } return g; } // Input of Edges template Edges esgraph([[maybe_unused]] int N, int M, int is_weighted = true, bool is_1origin = true) { Edges es; for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; es.emplace_back(x, y, c); } return es; } // Input of Adjacency Matrix template vector> adjgraph(int N, int M, T INF, int is_weighted = true, bool is_directed = false, bool is_1origin = true) { vector> d(N, vector(N, INF)); for (int _ = 0; _ < M; _++) { int x, y; cin >> x >> y; T c; if (is_weighted) cin >> c; else c = 1; if (is_1origin) x--, y--; d[x][y] = c; if (!is_directed) d[y][x] = c; } return d; } /** * @brief グラフテンプレート * @docs docs/graph/graph-template.md */ #line 6 "tree/euler-tour.hpp" template struct EulerTour { private: struct RMQ { int n, s; using P = pair; vector

seg; P UNIT = P(1 << 30, -1); RMQ(int N) : n(N), s(1) { while (s < N) s <<= 1; seg.assign(2 * s, UNIT); } void set(int k, P x) { seg[k + s] = x; } P operator[](int k) const { return seg[k + s]; } void build() { for (int k = s - 1; k > 0; k--) { seg[k] = min(seg[2 * k], seg[2 * k + 1]); } } P query(int a, int b) const { P R = UNIT; for (a += s, b += s; a < b; a >>= 1, b >>= 1) { if (a & 1) R = min(R, seg[a++]); if (b & 1) R = min(R, seg[--b]); } return R; } int size() const { return n; } }; vector down, up; int id; RMQ rmq; void init(G &g, int root) { dfs(g, root, -1, 0); if (id < rmq.size()) rmq.set(id++, {-1, -1}); for (int i = 0; i < (int)g.size(); i++) { if (down[i] == -1) { rmq.set(id++, {-1, -1}); dfs(g, i, -1, 0); if (id < rmq.size()) rmq.set(id++, {-1, -1}); } } rmq.build(); } void dfs(G &g, int c, int p, int dp) { down[c] = id; rmq.set(id++, {dp, c}); for (auto &d : g[c]) { if (d == p) continue; dfs(g, d, c, dp + 1); } up[c] = id; if (p != -1) rmq.set(id++, {dp - 1, p}); } public: // remind : because of additional node, // DS on tour should reserve 2 * n nodes. EulerTour(G &g, int root = 0) : down(g.size(), -1), up(g.size(), -1), id(0), rmq(2 * g.size()) { init(g, root); } pair idx(int i) const { return {down[i], up[i]}; } int lca(int a, int b) const { if (down[a] > down[b]) swap(a, b); return rmq.query(down[a], down[b] + 1).second; } template void node_query(int a, int b, const F &f) { int l = lca(a, b); f(down[l], down[a] + 1); f(down[l] + 1, down[b] + 1); } template void edge_query(int a, int b, const F &f) { int l = lca(a, b); f(down[l] + 1, down[a] + 1); f(down[l] + 1, down[b] + 1); } template void subtree_query(int a, const F &f) { f(down[a], up[a]); } int size() const { return int(rmq.size()); } }; /** * @brief オイラーツアー * @docs docs/tree/euler-tour.md */ using ll = long long; using pll = pair; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; ll r, b; cin >> n >> r >> b; UnweightedGraph g(n); vector dr(n), db(n); for (ll i = 1; i <= n; i++) { ll a = (i + isqrt(5 * i * i)) / 2; ll c = i + a; int p = int(i - 1); if (a != i && a <= n) { int v = int(a - 1); g[p].push_back(v); g[v].push_back(p); dr[v] = dr[p] + 1; db[v] = db[p]; } if (c <= n) { int v = int(c - 1); g[p].push_back(v); g[v].push_back(p); dr[v] = dr[p]; db[v] = db[p] + 1; } } EulerTour et(g, 0); vector down(n); for (int v = 0; v < n; v++) { down[v] = et.idx(v).first; } auto d = [&](int u, int v) -> pll { int w = et.lca(u, v); return { dr[u] + dr[v] - 2 * dr[w], db[u] + db[v] - 2 * db[w], }; }; set> white; ll cr = 0, cb = 0; int q; cin >> q; while (q--) { int type; ll x; cin >> type >> x; if (type == 1) { int v = int(x - 1); pair key{down[v], v}; auto it = white.lower_bound(key); bool is_white = it != white.end() && *it == key; if (!is_white) { if (!white.empty()) { auto next_it = (it == white.end() ? white.begin() : it); auto prev_it = (it == white.begin() ? prev(white.end()) : prev(it)); int s = prev_it->second; int t = next_it->second; auto [svr, svb] = d(s, v); auto [vtr, vtb] = d(v, t); auto [str, stb] = d(s, t); cr += (svr + vtr - str) / 2; cb += (svb + vtb - stb) / 2; } white.insert(key); } else { if (white.size() >= 2) { auto next_it = next(it); if (next_it == white.end()) { next_it = white.begin(); } auto prev_it = (it == white.begin() ? prev(white.end()) : prev(it)); int s = prev_it->second; int t = next_it->second; auto [svr, svb] = d(s, v); auto [vtr, vtb] = d(v, t); auto [str, stb] = d(s, t); cr -= (svr + vtr - str) / 2; cb -= (svb + vtb - stb) / 2; } white.erase(it); } } else if (type == 2) { r = x; } else { b = x; } cout << r * cr + b * cb << '\n'; } }