제출 #382716

#제출 시각아이디문제언어결과실행 시간메모리
382716maximath_1Birthday gift (IZhO18_treearray)C++11
0 / 100
46 ms48128 KiB
#include <stdio.h> #include <string> #include <math.h> #include <algorithm> #include <vector> #include <string.h> #include <numeric> #include <queue> #include <assert.h> #include <map> #include <set> #include <limits.h> using namespace std; #define ll long long #define ld long double const int MX = 200005; const int LG = (int)log2(MX) + 2; const ll mod = 1e9 + 7; const ll inv2 = (mod + 1) / 2; #define gc getchar//_unlocked //can't for window server void cin(int &x){ char c = gc(); bool neg = false; for(; c < '0'||'9' < c; c = gc()) if(c == '-') neg=true; x = c - '0'; c = gc(); for(; '0' <= c && c <= '9'; c = gc()) x = (x << 1) + (x << 3) + (c - '0'); if(neg) x = -x; } int n, m, q, a[MX]; vector<int> adj[MX]; set<int> ans_1[MX], ans_2[MX]; int anc[MX][LG], depth[MX]; void dfs(int nw, int bf){ anc[nw][0] = bf; depth[nw] = depth[bf] + 1; for(int nx : adj[nw]) if(nx != bf) dfs(nx, nw); } void build_lca(){ for(int j = 1; j < LG; j ++) for(int i = 1; i <= n; i ++) anc[i][j] = anc[anc[i][j - 1]][j - 1]; } int lca(int u, int v){ if(depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for(int i = LG - 1; i >= 0; i --) if(diff & (1 << i)) u = anc[u][i]; if(u == v) return u; for(int i = LG - 1; i >= 0; i --) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i]; return anc[u][0]; } int main(){ cin(n); cin(m); cin(q); for(int u, v, i = 1; i < n; i ++){ cin(u); cin(v); adj[u].push_back(v); adj[v].push_back(u); } dfs(1, 1); build_lca(); for(int i = 1; i <= m; i ++){ cin(a[i]); ans_1[a[i]].insert(i); } for(int i = 1; i < m; i ++){ int lc = lca(a[i], a[i + 1]); ans_2[lc].insert(i); } for(int tp, l, r, ps, v; q --;){ cin(tp); if(tp == 1){ cin(ps); cin(v); if(ps > 1){ int get = lca(a[ps - 1], a[ps]); ans_2[get].erase(ans_2[get].find(ps - 1)); get = lca(a[ps - 1], v); ans_2[get].insert(ps - 1); } if(ps < m){ int get = lca(a[ps], a[ps + 1]); ans_2[get].erase(ans_2[get].find(ps)); get = lca(a[ps], v); ans_2[get].insert(ps); } ans_1[a[ps]].erase(ans_1[a[ps]].find(ps)); a[ps] = v; ans_1[a[ps]].insert(ps); }else{ cin(l); cin(r); cin(v); auto it = ans_2[v].lower_bound(l); if(it != ans_2[v].end() && l <= *it && *it + 1 <= r) printf("%d %d\n", *it, *it + 1); else{ it = ans_1[v].lower_bound(l); if(it != ans_1[v].end() && l <= *it && *it <= r) printf("%d %d\n", *it, *it); else printf("-1 -1\n"); } } } 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...