제출 #760342

#제출 시각아이디문제언어결과실행 시간메모리
760342NK_Birthday gift (IZhO18_treearray)C++17
100 / 100
1099 ms81960 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define pb push_back #define f first #define s second #define mp make_pair using pi = pair<int, int>; // const int nax = 2e5+5; // const int LG = 18; template<class T> using V = vector<T>; int main() { cin.tie(0)->sync_with_stdio(0); int N, M, Q; cin >> N >> M >> Q; int LG = 0; while((1 << LG) < N) LG++; V<V<int>> up(N, V<int>(LG)); V<int> dep(N); V<V<int>> adj(N); for(int _ = 0; _ < N-1; _++) { int u, v; cin >> u >> v; --u, --v; adj[u].pb(v); adj[v].pb(u); } function<int(int, int)> jmp = [&] (int u, int d) { for(int i = 0; i < LG; i++) if ((d >> i) & 1) { u = up[u][i]; } return u; }; function<int(int, int)> lca = [&](int a, int b) { if (dep[a] < dep[b]) swap(a, b); a = jmp(a, dep[a] - dep[b]); if (a == b) return a; for(int i = LG - 1; i >= 0; i--) { if (up[a][i] != up[b][i]) a = up[a][i], b = up[b][i]; } return up[a][0]; }; function<void(int, int)> dfs = [&](int u, int p) { up[u][0] = p; for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1]; for(auto v : adj[u]) if (v != p) { dep[v] = dep[u] + 1; dfs(v, u); } }; dep[0] = 0; dfs(0, 0); V<set<pi>> X(N); V<int> A(M), LCA(M-1); for(auto& x : A) { cin >> x; --x; } for(int i = 0; i < M; i++) { if (i+1 < M) X[(LCA[i] = lca(A[i], A[i+1]))].insert(mp(i, i+1)); X[A[i]].insert(mp(i, i)); } while(Q--) { int t; cin >> t; if (t == 1) { int i, x; cin >> i >> x; --i, --x; if (i-1 >= 0) X[LCA[i-1]].erase(mp(i-1, i)); if (i+1 < M) X[LCA[i]].erase(mp(i, i+1)); X[A[i]].erase(mp(i, i)); A[i] = x; X[A[i]].insert(mp(i, i)); if (i-1 >= 0) X[(LCA[i-1] = lca(A[i-1], A[i]))].insert(mp(i-1, i)); if (i+1 < M) X[(LCA[i] = lca(A[i], A[i+1]))].insert(mp(i, i+1)); } else { int l, r, x; cin >> l >> r >> x; --l, --r, --x; // --r; // BECAUSE NEED TO FIND i SUCH THAT l ≤ i < r // for(auto v : X[x]) cout << "(" << v.f << ", " << v.s << ")" << nl; // cout << nl; auto it = X[x].lower_bound(mp(l, -1)); if (it == end(X[x])) cout << -1 << " " << -1 << nl; else { int L, R; tie(L, R) = *it; if (R > r) L = R = -1; else ++L, ++R; cout << L << " " << R << nl; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...