Submission #909778

#	Time	Username	Problem	Language	Result	Execution time	Memory
909778		daoquanglinh2007	Birthday gift (IZhO18_treearray)	C++17	0 / 100	5 ms	16508 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
 
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 2e5, LOG = 18;
 
int n, m, q;
vector <int> adj[NM+5];
int dep[NM+5], timer = 0, tin[NM+5], tout[NM+5];
pii f[LOG+5][2*NM+5];
int a[NM+5];
set <pii> S1, S2;
set <pii>::iterator it;
 
void dfs(int u, int p){
	dep[u] = (p == -1 ? 0 : dep[p]+1);
	tin[u] = ++timer;
	f[0][timer] = mp(dep[u], u);
	for (int v : adj[u]){
		if (v == p) continue;
		dfs(v, u);
		f[0][++timer] = mp(dep[u], u);
	}
	tout[u] = timer;
}
 
void build_sparse(){
	for (int i = 1; i <= LOG; i++)
		for (int j = 1; j+(1<<i)-1 <= timer; j++)
			f[i][j] = min(f[i-1][j], f[i-1][j+(1<<(i-1))]);
}
 
int lca(int l, int r){
	l = tin[l], r = tin[r];
	if (l > r) swap(l, r);
	int k = __lg(r-l+1);
	return min(f[k][l], f[k][r-(1<<k)+1]).se;
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m >> q;
	for (int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, -1);
	build_sparse();
	
	for (int i = 1; i <= m; i++) cin >> a[i];
	for (int i = 1; i <= m; i++){
		S1.insert(mp(a[i], i));
		if (i < m) S2.insert(mp(lca(a[i], a[i+1]), i));
	}
	
	while (q--){
		int type; cin >> type;
		if (type == 1){
			int pos, val; cin >> pos >> val;
			S1.erase(mp(a[pos], pos));
			if (pos > 1) S2.erase(mp(lca(a[pos-1], a[pos]), pos-1));
			if (pos < m) S2.erase(mp(lca(a[pos], a[pos+1]), pos));
			a[pos] = val;
			S1.insert(mp(a[pos], pos));
			if (pos > 1) S2.insert(mp(lca(a[pos-1], a[pos]), pos-1));
			if (pos < m) S2.insert(mp(lca(a[pos], a[pos+1]), pos));
		}
		else{
			int l, r, v; cin >> l >> r >> v;
			it = S1.lower_bound(mp(v, l));
			if (it != S1.end() && it->se <= r){
				cout << it->se << ' ' << it->se << '\n';
				continue;
			}
			it = S2.lower_bound(mp(v, l));
			if (it != S2.end() && it->se < r){
				cout << it->se << ' ' << it->se+1 << '\n';
				continue;
			}
			cout << "-1 -1\n";
		}
	}
	return 0;
}

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