제출 #893993

#제출 시각아이디문제언어결과실행 시간메모리
893993azosiMin-max tree (BOI18_minmaxtree)C++17
0 / 100
181 ms28168 KiB
#include <bits/stdc++.h> #define x first #define y second using namespace std; const int MAX_N = 70002; const int INF = 1e9 + 1000; vector<int> g[MAX_N], tree[MAX_N]; int n, k; struct SegmentTree { typedef int (*F)(int, int); F merge; int identity; int tree[MAX_N * 4]{}, lazy[MAX_N * 4]{}; SegmentTree(F func, int identity) : merge(func), identity(identity) { for (int i = 0; i < MAX_N * 4; ++i) tree[i] = lazy[i] = identity; } void push(int node, int l, int r) { if (lazy[node] != identity) { tree[node] = merge(tree[node], lazy[node]); if (l != r) { lazy[node * 2] = merge(lazy[node * 2], lazy[node]); lazy[node * 2 + 1] = merge(lazy[node * 2 + 1], lazy[node]); } } lazy[node] = identity; } void update(int s, int e, int val, int node = 1, int l = 1, int r = n) { push(node, l, r); if (e < l || r < s) return; if (s <= l && r <= e) { lazy[node] = val; push(node, l, r); return; } int mid = (l + r) / 2; update(s, e, val, node * 2, l, mid); update(s, e, val, node * 2 + 1, mid + 1, r); tree[node] = merge(tree[node * 2], tree[node * 2 + 1]); } int query(int s, int e, int node = 1, int l = 1, int r = n) { push(node, l, r); if (e < l || r < s) return identity; if (s <= l && r <= e) return tree[node]; int mid = (l + r) / 2; return merge(query(s, e, node * 2, l, mid), query(s, e, node * 2 + 1, mid + 1, r)); } }; int _mn(int a, int b) { return min(a, b); } int _mx(int a, int b) { return max(a, b); } SegmentTree minSeg(_mn, INF); SegmentTree maxSeg(_mx, -INF); void makeTree(int here = 1, int prev = 0) { for (auto there: g[here]) { if (there == prev) continue; tree[here].push_back(there); makeTree(there, here); } } int sz[MAX_N], dep[MAX_N], par[MAX_N], top[MAX_N], in[MAX_N]; void dfs1(int here = 1) { sz[here] = 1; for (auto &there: tree[here]) { dep[there] = dep[here] + 1; par[there] = here; dfs1(there); sz[here] += sz[there]; if (sz[there] > sz[tree[here][0]]) swap(there, tree[here][0]); } } int counter; void dfs2(int here = 1) { in[here] = ++counter; for (auto there: tree[here]) { top[there] = there == tree[here][0] ? top[here] : there; dfs2(there); } } void update(int a, int b, int val, bool qType) { while (top[a] != top[b]) { if (dep[top[a]] < dep[top[b]]) swap(a, b); int st = top[a]; qType ? minSeg.update(in[st], in[a], val) : maxSeg.update(in[st], in[a], val); a = par[st]; } if (a == b) return; if (dep[a] > dep[b]) swap(a, b); qType ? minSeg.update(in[a] + 1, in[b], val) : maxSeg.update(in[a] + 1, in[b], val); } pair<int, int> query(int a, int b) { pair<int, int> ret = {INF, -INF}; while (top[a] != top[b]) { if (dep[top[a]] < dep[top[b]]) swap(a, b); int st = top[a]; ret.first = min(ret.first, minSeg.query(in[st], in[a])); ret.second = max(ret.second, maxSeg.query(in[st], in[a])); a = par[st]; } if (a == b) return ret; if (dep[a] > dep[b]) swap(a, b); ret.first = min(ret.first, minSeg.query(in[a] + 1, in[b])); ret.second = max(ret.second, maxSeg.query(in[a] + 1, in[b])); return ret; } struct Query { int s, e, x, mx; }; map<int, int> mp; int cnt[70707], ans[70707]; int vis[70707], chk[70707]; vector<int> track[70707]; vector<Query> qry; int mn[70707], mx[70707]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } cin >> k; makeTree(); dfs1(); dfs2(); vector<int> zz; for (int i = 0; i < k; ++i) { char q; int x, y, z; cin >> q >> x >> y >> z; if (q == 'M') { update(x, y, z, false); } else { update(x, y, z, true); } qry.push_back({x, y, z, q == 'M'}); } map<int, int> idx; for (int i = 0; i < k; i++) mp[qry[i].x] = i; for (int i = 2; i <= n; i++) { mn[i] = maxSeg.query(in[i], in[i]); mx[i] = minSeg.query(in[i], in[i]); if (mn[i] != -INF) { cnt[mp[mn[i]]]++; track[mp[mn[i]]].push_back(i); } if (mx[i] != INF) { cnt[mp[mx[i]]]++; track[mp[mx[i]]].push_back(i); } } memset(chk, 0, sizeof chk); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<> > pq; for (int i = 0; i < k; i++) pq.push({cnt[mp[qry[i].x]], i}); while (!pq.empty()) { pair<int, int> now = pq.top(); pq.pop(); if (now.x != cnt[now.y]) continue; vis[now.y] = true; for (int i: track[now.y]) { if (chk[i]) continue; ans[i] = qry[now.y].x; chk[i] = true; if (qry[now.y].mx) { if (mn[i] != -INF) { cnt[mp[mn[i]]]--; if (!vis[mp[mn[i]]]) pq.push({cnt[mp[mn[i]]], mp[mn[i]]}); } } else { if (mx[i] != INF) { cnt[mp[mx[i]]]--; if (!vis[mp[mx[i]]]) pq.push({cnt[mp[mx[i]]], mp[mx[i]]}); } } break; } } for (int i = 2; i <= n; i++) if (!chk[i]) ans[i] = mn[i]; for (int i = 2; i <= n; i++) { cout << par[i] << " " << i << " " << ans[i] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...