Submission #441946

#	Time	Username	Problem	Language	Result	Execution time	Memory
441946		Nima_Naderi	Birthday gift (IZhO18_treearray)	C++14	0 / 100	36 ms	52088 KiB

treearray

//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> data;
const ll MXN = 2e5 + 10;
const ll MXS = MXN * 4;
const ll LOG = 18;
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<data> 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(data 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){
		data 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);
}
set<ll> my[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;
		data now = Mp(Mp(Stm[x], Ftm[x]), i);
		Ins(now, 1, i);
		A[i] = x;
	}
	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){
			data 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);
			}
			A[x] = y;
			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(my[z].size()){
				auto itr = my[z].lower_bound(x + 1);
				if(itr != my[z].end() && *itr <= y){
					cout << *itr - 1 << ' ' << *itr << '\n';
					ans = 0;
				}
			}		
			if(ans) cout << -1 << ' ' << -1 << '\n';
		}
	}
	return 0;
}
// N.N

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 26
• Subtask 4: 0 / 44