Submission #492387

#	Time	Username	Problem	Language	Result	Execution time	Memory
492387		vuhoanggiap	Birthday gift (IZhO18_treearray)	C++17	100 / 100	830 ms	102348 KiB

treearray

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

const int maxN = 2e5 + 1; 
int n, m, q; 
vector<int> adj[maxN]; 

int f[maxN], s[2 * maxN], euler;  
int h[maxN]; 

void dfs(int u, int p = 1) {
	s[++euler] = u; 
	f[u] = euler; 
	for (auto v : adj[u]) {
		if (v == p)
			continue; 
		h[v] = h[u] + 1; 
		dfs(v, u); 
		s[++euler] = u; 
	}
}

int lg[2 * maxN]; 
int sp[2 * maxN][20]; 

void build() {
	lg[1] = 0; 
	for (int i = 2; i <= euler; i++) 
		lg[i] = lg[i >> 1] + 1; 
	for (int len = 0; (1 << len) <= euler; len++) {
		for (int i = 1; i + (1 << len) - 1 <= euler; i++) {
			if (!len) 
				sp[i][0] = s[i]; 
			else {
				if (h[sp[i][len - 1]] < h[sp[i + (1 << (len - 1))][len - 1]])
					sp[i][len] = sp[i][len - 1]; 
				else 
					sp[i][len] = sp[i + (1 << (len - 1))][len - 1]; 
			}
		}
	}
}

int lca(int u, int v) {
	int l = f[u], r = f[v]; 
	if (l > r) 
		swap(l, r); 
	int Lg = lg[r - l + 1]; 
	if (h[sp[l][Lg]] < h[sp[r - (1 << Lg) + 1][Lg]])
		return sp[l][Lg]; 
	return sp[r - (1 << Lg) + 1][Lg]; 
}

int a[maxN]; 
set<int> id[maxN], id2[maxN]; 

void add(int i) { 
	if (!i || i == n) 
		return; 
	int val = lca(a[i], a[i + 1]); 
	id2[val].insert(i); 
}

void rem(int i) {
	if (!i || i == n) 
		return; 
	int val = lca(a[i], a[i + 1]); 
	id2[val].erase(i);
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	cin >> n >> m >> q; 
	for (int i = 1; i < n; i++) {
		int u, v; cin >> u >> v; 
		adj[u].pb(v); adj[v].pb(u); 
	}
//5 4 4
//1 2
//3 1
//3 4
//5 3
//4 5 2 3
//2 1 3 1
//1 3 5
//2 3 4 5
//2 1 3 1
	dfs(1); 
	build();
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
		id[a[i]].insert(i); 
		add(i - 1); 
	}
//	cout << "id: "; for (int i = 1; i <= n; i++) {
//		cout << "val: " << i << '\t'; 
//		for (auto x : id[i]) cout << x << ' '; cout << '\n'; 
//	}
//	cout << "id2: "; 
//	for (int i = 1; i <= n; i++) {
//		cout << "val: " << i << '\t'; 
//		for (auto x : id2[i]) cout << x << ' '; cout << '\n'; 
//	}
	for (int i = 1; i <= q; i++) {
		int type; cin >> type; 
		if (type == 1) {
			int pos, v; cin >> pos >> v; 
			id[a[pos]].erase(pos); 
			rem(pos - 1); 
			rem(pos); 
			a[pos] = v; 
			add(pos); 
			add(pos - 1); 
			id[a[pos]].insert(pos); 
		}
		else {
			int l, r, v; cin >> l >> r >> v; 
			set<int>::iterator it = id[v].lower_bound(l); 
			bool foundAns = false; 
			if (it != id[v].end()) {
				int val = *it; 
				if (val <= r) {
					cout << val << ' ' << val << '\n';
					foundAns = true;  
				}
			}
			it = id2[v].lower_bound(l); 
			if (it != id2[v].end() && !foundAns) {
				int val = *it; 
				if (val < r) {
					cout << val << ' ' << val + 1 << '\n'; 
					foundAns = true; 
				}
			}
			if (!foundAns) 
				cout << -1 << ' ' << -1 << '\n'; 
		}
	}
}

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