이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//In the name of God
#include<bits/stdc++.h>
#define lc (id * 2)
#define rc (id * 2 + 1)
#define md ((s + e) / 2)
#define dm ((s + e) / 2 + 1)
#define ln (e - s + 1)
#define Mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<pll, ll> nima;
const ll MXN = 3e5 + 10;
const ll MXS = MXN * 4;
const ll LOG = 20;
ll n, m, q, timer;
ll Jad[LOG][MXN], dis[MXN];
ll Stm[MXN], Ftm[MXN], A[MXN], Arr[MXN];
vector<ll> adj[MXN];
multiset<nima> seg[MXS];
void prep(ll u, ll par){
Stm[u] = ++ timer; Arr[timer] = u;
Jad[0][u] = par;
for(int i = 1; i < LOG; i ++){
Jad[i][u] = Jad[i - 1][Jad[i - 1][u]];
}
for(auto v : adj[u]){
if(v != par) dis[v] = dis[u] + 1, prep(v, u);
}
Ftm[u] = timer;
}
ll K_Jad(ll u, ll k){
for(int i = 0; i < LOG; i ++){
if((k >> i) & 1LL) u = Jad[i][u];
}
return u;
}
ll LCA(ll u, ll v){
if(dis[u] > dis[v]) swap(u, v);
v = K_Jad(v, dis[v] - dis[u]);
if(u == v) return v;
for(int i = LOG - 1; ~i; i --){
if(Jad[i][u] != Jad[i][v]){
u = Jad[i][u], v = Jad[i][v];
}
}
return Jad[0][u];
}
bool Is_Jad(ll j, ll u){
return Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j];
}
void Ins(nima x, ll tp, ll p, ll id = 1, ll s = 1, ll e = m){
if(tp) seg[id].insert(x);
else seg[id].erase(seg[id].find(x));
if(ln == 1) return;
if(p <= md) Ins(x, p, lc, s, md);
else Ins(x, p, rc, dm, e);
}
ll Get(ll l, ll r, ll stm, ll ftm, ll id = 1, ll s = 1, ll e = m){
if(e < l || s > r) return -1;
if(l <= s && e <= r){
nima nw = Mp(Mp(stm, -1), -1);
auto itr = seg[id].lower_bound(nw);
if(itr == seg[id].end() || itr -> first.second > ftm) return -1;
return itr -> second;
}
ll nw = Get(l, r, stm, ftm, lc, s, md);
if(nw != -1) return nw;
return Get(l, r, stm, ftm, rc, dm, e);
}
multiset<ll> my[MXN], sm[MXN];
int main(){
ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
assert(1LL << LOG > MXN);
cin >> n >> m >> q;
for(int i = 1; i < n; i ++){
ll u, v; cin >> u >> v;
adj[u].push_back(v), adj[v].push_back(u);
}
prep(1, 0);
for(int i = 1, x; i <= m; i ++){
cin >> x;
nima now = Mp(Mp(Stm[x], Ftm[x]), i);
//Ins(now, 1, i);
A[i] = x;
sm[x].insert(i);
}
for(int i = 2; i <= m; i ++){
ll x = LCA(A[i - 1], A[i]);
my[x].insert(i);
}
while(q --){
ll t, x, y, z; cin >> t >> x >> y;
if(t == 1){
nima now = Mp(Mp(Stm[A[x]], Ftm[A[x]]), x);
//Ins(now, 0, x);
if(x + 1 <= n){
ll xp = LCA(A[x], A[x + 1]);
my[xp].erase(x + 1);
}
if(x - 1 >= 1){
ll xp = LCA(A[x - 1], A[x]);
my[xp].erase(x);
}
sm[A[x]].erase(x);
A[x] = y;
sm[A[x]].insert(x);
now = Mp(Mp(Stm[A[x]], Ftm[A[x]]), x);
//Ins(now, 1, x);
if(x + 1 <= m){
ll xp = LCA(A[x], A[x + 1]);
my[xp].insert(x + 1);
}
if(x - 1 >= 1){
ll xp = LCA(A[x - 1], A[x]);
my[xp].insert(x);
}
} else {
cin >> z; ll /*ans = Get(x, y, Stm[z], Ftm[z]);
if(ans == -1){
cout << -1 << ' ' << -1 << '\n';
continue;
}
ll kid = A[ans];
if(kid == z){
cout << ans << ' ' << ans << '\n';
continue;
}*/
ans = 1;
if(sm[z].size()){
auto itr = sm[z].lower_bound(x);
if(itr != sm[z].end() && *itr <= y){
cout << *itr << ' ' << *itr << '\n';
ans = 0;
}
}
if(ans && my[z].size()){
auto itr = my[z].lower_bound(x + 1);
if(itr != my[z].end() && *itr <= y){
assert(LCA(A[*itr - 1], A[*itr]) == z);
cout << *itr - 1 << ' ' << *itr << '\n';
ans = 0;
}
}
if(ans) cout << -1 << ' ' << -1 << '\n';
}
}
return 0;
}
// N.N
컴파일 시 표준 에러 (stderr) 메시지
treearray.cpp: In function 'int main()':
treearray.cpp:86:8: warning: variable 'now' set but not used [-Wunused-but-set-variable]
86 | nima now = Mp(Mp(Stm[x], Ftm[x]), i);
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |