Submission #1235132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235132		nlsosad	Birthday gift (IZhO18_treearray)	C++20	56 / 100	161 ms	53032 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
vector<int> adj[200001];
int bin[200001][18];
int a[200001];
int depth[200001];
int b[200001];
set<int> la[200001], lb[20001];
void dfs(int i, int p){
	for (int j:adj[i]){
		if(j!=p){
			depth[j] = depth[i] + 1;
			bin[j][0]= i;
			dfs(j, i);
		}
	}
}
int lca(int u, int v){
	if(depth[u] < depth[v]){
		swap(u, v);
	}
	int diff = depth[u] - depth[v];
	for (int i = 0;i<18;++i){
		if(diff & (1<<i)){
			u = bin[u][i];
		}
	}
	if(u==v)return u;
	for (int i=17;i>=0;--i){
		if(bin[u][i]!=bin[v][i]){
			u = bin[u][i];
			v = bin[v][i];
		}
	}
	return bin[u][0];
}
int main(){
	int n, m ,q;
	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);
	}
	for (int i = 1;i<=m;++i){
		cin >> a[i];
	}
	dfs(1, 0);
	for (int j = 1;j<18;++j){
		for (int i = 1;i<=n;++i){
			bin[i][j] = bin[bin[i][j-1]][j-1];
		}
	}
	for (int i = 1;i<m;++i){
		b[i] = lca(a[i], a[i+1]);
		la[a[i]].insert(i);
		lb[b[i]].insert(i);
	}
	la[a[m]].insert(m);
	while(q--){
		int t;
		cin >> t;
		if(t==1){
			int pos, v;
			cin >> pos >> v;
			la[a[pos]].erase(pos);
			if(pos < n){
				lb[b[pos]].erase(pos);
			}
			if(pos>1){
				lb[b[pos-1]].erase(pos-1);
			}
			a[pos] = v;
			la[a[pos]].insert(pos);
			if(pos < n){
				b[pos] = lca(a[pos], a[pos+1]);
				lb[b[pos]].insert(pos);
			}
			if(pos>1){
				b[pos-1] = lca(a[pos-1], a[pos]);
				lb[b[pos-1]].insert(pos-1);
			}
		}else{
			int l, r, v;
			cin >> l >> r >> v;
			int x = -1, y = -1;
			auto it = la[v].lower_bound(l);
			if(it!=la[v].end() and *it <= r){
				x = *it;
				y = *it;
			}else{
				it = lb[v].lower_bound(l);
				if(it!=lb[v].end() and *it < r){
					x = *it;
					y = *it + 1;
				}
			}
			cout << x << ' ' << y << '\n';
		}
	}
}

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