Submission #1163266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163266		Muaath_5	Birthday gift (IZhO18_treearray)	C++20	100 / 100	648 ms	75644 KiB

treearray

// Problem: F - Ш
// Contest: Virtual Judge - 2024-03-04
// URL: https://vjudge.net/contest/698802#problem/F
// 
// By Muaath Alqarni
// Blog: https://muaath.dev/blog

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2e5+1, LG = 19;

int n, m, q, a[N];
vector<int> adj[N];

int dep[N], st[N][LG];
void dfs(int node=1, int par=1) {
	st[node][0] = par;
	dep[node] = dep[par]+1;
	for (int ch : adj[node])
		if (ch ^ par)
			dfs(ch, node);
}
void build_lca() {
	dfs();
	for (int j = 1; j < LG; j++)
		for (int i = 1; i <= n; i++)
			st[i][j] = st[st[i][j-1]][j-1];
}
int jmp(int x, int k) {
	for (int i = 0; i < LG; i++)
		if (k>>i&1)
			x = st[x][i];
	return x;
}
int lca(int u, int v) {
	if (dep[u] < dep[v]) swap(u, v);
	u = jmp(u, dep[u]-dep[v]);
	if (u == v) return u;
	for (int i = LG-1; i >= 0; i--)
		if (st[u][i] != st[v][i])
			u = st[u][i], v = st[v][i];
	return st[u][0];
}

set<int> rng1[N];
set<int> rng2[N];

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 0; i < n-1; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);	
	}
	build_lca();
	for (int i = 1; i <= m; cin >> a[i++]);
	
	for (int i = 1; i <= m; i++) {
		rng1[a[i]].insert(i);
	}
	for (int i = 1; i < m; i++) {
		rng2[lca(a[i], a[i+1])].insert(i);
	}
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			
			int p, v;
			cin >> p >> v;
			rng1[a[p]].erase(p);
			rng2[lca(a[p], a[p+1])].erase(p);
			rng2[lca(a[p-1], a[p])].erase(p-1);
			a[p] = v;
			rng1[a[p]].insert(p);
			rng2[lca(a[p], a[p+1])].insert(p);
			rng2[lca(a[p-1], a[p])].insert(p-1);
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			auto it1 = rng1[v].lower_bound(l);
			if (it1 != rng1[v].end() && *it1 <= r) {
				cout << *it1 << ' ' << *it1 << '\n';
				continue;	
			}
			auto it2 = rng2[v].lower_bound(l);
			if (it2 != rng2[v].end() && *it2 < r) {
				cout << *it2 << ' ' << *it2 + 1 << '\n';
				continue;	
			}
			
			cout << "-1 -1\n";
		}
	}
}

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