Submission #1244629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244629		altern23	Birthday gift (IZhO18_treearray)	C++20	0 / 100	3 ms	5188 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 2e5;
const ll INF = 1e18;
const int MOD = 998244353;
const ld eps = 1e-6;

vector<ll> adj[MAXN + 5];
ll up[MAXN + 5][20], a[MAXN + 5], dist[MAXN + 5];

void dfs(ll idx, ll par){
	for(auto i : adj[idx]){
		if(i != par){
			up[i][0] = idx;
			dist[i] = dist[idx] + 1;
			dfs(i, idx);
		}
	}
}

ll get_lca(ll a, ll b){
	if(dist[a] < dist[b]) swap(a, b);
	ll need = dist[a] - dist[b];
	for(int i = 0; i < 20; i++){
		if(need & (1LL << i)) a = up[a][i];
	}
	if(a == b) return a;
	for(int i = 19; i >= 0; --i){
		if(up[a][i] != up[b][i]) a = up[a][i], b = up[b][i];
	}
	return up[a][0];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);		
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, M, Q; cin >> N >> M >> Q;
		for(int i = 2; i <= N; i++){
			ll u, v; cin >> u >> v;
			adj[u].push_back(v), adj[v].push_back(u);
		}
		dfs(1, -1);
		for(int log = 1; log < 20; log++){
			for(int i = 1; i <= N; i++){
				up[i][log] = up[up[i][log]][log - 1];
			}
		}
		set<pii> cnt[N + 5];
		for(int i = 1; i <= M; i++){
			cin >> a[i];
			cnt[a[i]].insert({i, i});
		}
		for(int i = 1; i <= M; i++){
			if(i > 1) cnt[get_lca(a[i], a[i - 1])].insert({i - 1, i});
			if(i < M) cnt[get_lca(a[i], a[i + 1])].insert({i, i + 1});
		}
		for(int i = 1; i <= Q; i++){
			ll t; cin >> t;
			if(t == 1){
				ll idx, val; cin >> idx >> val;
				cnt[a[idx]].erase({idx, idx});
				if(idx > 1) cnt[get_lca(a[idx], a[idx - 1])].erase({idx - 1, idx});
				if(idx < M) cnt[get_lca(a[idx], a[idx + 1])].erase({idx, idx + 1});
				a[idx] = val;
				cnt[a[idx]].insert({idx, idx});
				if(idx > 1) cnt[get_lca(a[idx], a[idx - 1])].insert({idx - 1, idx});
				if(idx < M) cnt[get_lca(a[idx], a[idx + 1])].insert({idx, idx + 1});
			}
			else{
				ll l, r, v; cin >> l >> r >> v;
				auto x = cnt[v].lower_bound({l, -INF});
				if(x != cnt[v].end() && (*x).sec <= r){
					cout << (*x).fi << " " << (*x).sec << "\n";
				}
				else cout << "-1 -1\n";
			}
		}
	}
}

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