제출 #345442

#제출 시각아이디문제언어결과실행 시간메모리
345442koketsuBirthday gift (IZhO18_treearray)C++14
100 / 100
1957 ms84220 KiB
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <iterator> using namespace std; #define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0); #define S second #define F first #define pb push_back #define nl '\n' #define NL cout << '\n'; #define EX exit(0) #define all(s) s.begin(), s.end() #define no_answer {cout << "NO"; exit(0);} #define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k) const long long mxn = 2e5 + 110; const long long mnn = 1e3 + 2; const long long mod = 1e9 + 7; const long long inf = 1e18; const long long OO = 1e9; typedef long long llong; typedef unsigned long long ullong; int n, m, q, d[mxn][20], lvl[mxn], a[mxn], ans[mxn]; vector<int> g[mxn]; set<int> st[mxn], stpos[mxn]; void dfs(int x, int p){ lvl[x] = lvl[p] + 1; d[x][0] = p; for(int i = 1; i <= 18; i++){ d[x][i] = d[d[x][i - 1]][i - 1]; } for(auto to : g[x]){ if(to != p) dfs(to, x); } } int lca(int u, int v){ if(lvl[u] < lvl[v]){ swap(u, v); } int dif = lvl[u] - lvl[v]; for(int j = 0; j <= 18; j++){ if((1 << j) & dif){ u = d[u][j]; } } if(u == v) return u; for(int i = 18; i >= 0; i--){ if(d[u][i] != d[v][i]){ u = d[u][i]; v = d[v][i]; } } return d[u][0]; } void replace_pair(int pos, int type, int x){ int anc = lca(a[pos], a[pos + type]); st[anc].erase(min(pos + type, pos)); anc = lca(a[pos + type], x); st[anc].insert(min(pos + type, pos)); } int main() { cin >> n >> m >> q; for(int i = 1; i < n; i++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); for(int i = 1; i <= m; i++){ cin >> a[i]; } for(int i = 1; i <= m; i++){ stpos[a[i]].insert(i); if(i != m){ int u = i, v = i + 1; int anc = lca(a[u], a[v]); st[anc].insert(u); } } for(int i = 1; i <= q; i++){ int t; cin >> t; if(t == 1){ int pos, b; cin >> pos >> b; if(pos != 1){ replace_pair(pos, -1, b); } if(pos != m){ replace_pair(pos, 1, b); } stpos[a[pos]].erase(pos); stpos[b].insert(pos); a[pos] = b; }else{ int l, r, b; cin >> l >> r >> b; set<int> :: iterator it = stpos[b].lower_bound(l); if(it != stpos[b].end() && l <= *it && *it <= r){ cout << *it << ' ' << *it << nl; continue; } it = st[b].lower_bound(l); if(it == st[b].end()) { cout << -1 << ' ' << -1 << nl; continue; } if(it == st[b].end()){ cout << -1 << ' ' << -1 << nl; continue; } if(l <= *it && *it + 1 <= r){ cout << *it << ' ' << *it + 1 << nl; }else{ cout << -1 << ' ' << -1 << nl; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...