제출 #879286

#제출 시각아이디문제언어결과실행 시간메모리
879286The_SamuraiBirthday gift (IZhO18_treearray)C++17
100 / 100
1187 ms84848 KiB
// I stand with PALESTINE //#pragma GCC optimize("Ofast,O3") //#pragma GCC target("avx,avx2") #include "bits/stdc++.h" using namespace std; using ll = long long; const int lg = 18; vector<vector<int>> g, jump; vector<int> tin, tout; int z; void dfs(int u) { if (u != 1) { for (int i = 1; i < lg; i++) { jump[i][u] = jump[i - 1][jump[i - 1][u]]; if (!jump[i][u]) break; } } tin[u] = z++; for (int v: g[u]) { if (jump[0][u] == v) continue; jump[0][v] = u; dfs(v); } tout[u] = z++; } bool isPar(int u, int v) { return tin[u] <= tin[v] and tout[v] <= tout[u]; } int lca(int u, int v) { if (v == 0 or isPar(u, v)) return u; if (u == 0 or isPar(v, u)) return v; for (int i = lg - 1; i >= 0; i--) { if (!jump[i][u] or isPar(jump[i][u], v)) continue; u = jump[i][u]; } return jump[0][u]; } struct SegTree { vector<set<pair<int, int>>> tree; int size; void init(int n) { size = 1; while (size < n) size *= 2; tree.assign(2 * size - 1, set<pair<int, int>>()); build(0, 0, size); } void build(int x, int lx, int rx) { for (int i = 0; i < rx - lx; i++) tree[x].emplace(0, i + lx); if (rx - lx == 1) return; int m = (lx + rx) >> 1; build(2 * x + 1, lx, m); build(2 * x + 2, m, rx); } int upd(int i, int v, int x, int lx, int rx) { if (rx - lx == 1) { int vv = tree[x].begin()->first; tree[x] = set<pair<int, int>>{make_pair(v, i)}; return vv; } int vv, m = (lx + rx) >> 1; if (i < m) vv = upd(i, v, 2 * x + 1, lx, m); else vv = upd(i, v, 2 * x + 2, m, rx); tree[x].erase(tree[x].find(make_pair(vv, i))); tree[x].emplace(v, i); return vv; } void upd(int i, int v) { upd(i, v, 0, 0, size); } int get(int l, int r, int v, int x, int lx, int rx) { if (l >= rx or lx >= r) return -1; if (l <= lx and rx <= r) { auto it = tree[x].lower_bound(make_pair(v, 0)); if (it != tree[x].end() and it->first == v) return it->second; return -1; } int m = (lx + rx) >> 1; int ans = get(l, r, v, 2 * x + 1, lx, m); if (ans != -1) return ans; ans = get(l, r, v, 2 * x + 2, m, rx); return ans; } int get(int l, int r, int v) { return get(l, r + 1, v, 0, 0, size); } }; void solve() { int n, m, q; cin >> n >> m >> q; g.assign(n + 1, {}); jump.assign(lg, vector<int>(n + 1)); tin.assign(n + 1, 0); tout.assign(n + 1, 0); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].emplace_back(v); g[v].emplace_back(u); } vector<int> a(m + 1); for (int i = 1; i <= m; i++) cin >> a[i]; dfs(1); vector<set<int>> v1(n + 1), v2(n + 1); for (int i = 1; i <= m; i++) v1[a[i]].insert(i); for (int i = 1; i < m; i++) v2[lca(a[i], a[i + 1])].insert(i); while (q--) { int op; cin >> op; if (op == 1) { int i; cin >> i; v1[a[i]].erase(i); if (i > 1) v2[lca(a[i - 1], a[i])].erase(i - 1); if (i < m) v2[lca(a[i], a[i + 1])].erase(i); cin >> a[i]; v1[a[i]].insert(i); if (i > 1) v2[lca(a[i - 1], a[i])].insert(i - 1); if (i < m) v2[lca(a[i], a[i + 1])].insert(i); } else { int l, r, root; cin >> l >> r >> root; auto it1 = v1[root].lower_bound(l); if (it1 != v1[root].end() and *it1 <= r) { cout << *it1 << ' ' << *it1 << '\n'; continue; } auto it2 = v2[root].lower_bound(l); if (it2 != v2[root].end() and *it2 < r) cout << *it2 << ' ' << *it2 + 1 << '\n'; else cout << "-1 -1\n"; } } } int main() { cin.tie(0)->sync_with_stdio(false); #ifdef sunnatov freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int q = 1; // cin >> q; while (q--) { solve(); cout << '\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...