Submission #947564

#	Time	Username	Problem	Language	Result	Execution time	Memory
947564		oblantis	Birthday gift (IZhO18_treearray)	C++17	0 / 100	9 ms	23900 KiB

treearray

//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 2e5 + 12;
vt<int> g[maxn];
set<int> nei[maxn], sing[maxn];
int dp[maxn], up[maxn][20], a[maxn];
void dfs(int v){
	for(auto i : g[v]){
		if(up[v][0] == i)continue;
		dp[i] = dp[v] + 1;
		up[i][0] = v;
		dfs(i);
	}
}
int lca(int x, int y){
	if(dp[x] > dp[y])swap(x, y);
	int k = dp[y] - dp[x], o = 0;
	while(k){
		if(k & 1)y = up[y][o];
		o++;
		k >>= 1;
	}
	if(x == y)return x;
	for(int i = 19; i >= 0; i--){
		if(up[x][i] != up[y][i]){
			x = up[x][i], y = up[y][i];
		}
	}
	return up[x][0];
}
void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 0, u, v; i < n - 1; i++){
		cin >> u >> v;
		g[u].pb(v), g[v].pb(u);
	}
	up[1][0] = 1;
	dfs(1);
	for(int i = 1; i < 20; i++){
		for(int j = 1; j <= n; j++)up[i][j] = up[up[i - 1][j]][j];
	}
	for(int i = 1; i <= m; i++){
		cin >> a[i];
		sing[a[i]].insert(i);
		if(i > 1){
			nei[lca(a[i], a[i - 1])].insert(i - 1);
		}
	}
	for(int i = 0; i < q; i++){
		int w;
		cin >> w;
		if(w == 1){
			int pos, v, head;
			cin >> pos >> v;
			if(pos > 1){
				head = lca(a[pos - 1], a[pos]);
				nei[head].erase(pos - 1);
				head = lca(a[pos - 1], v);
				nei[head].insert(pos - 1);
			}
			if(pos < n){
				head = lca(a[pos], a[pos + 1]);
				nei[head].erase(pos);
				head = lca(v, a[pos + 1]);
				nei[head].insert(pos);	
			}
			sing[a[pos]].erase(pos);
			a[pos] = v;
			sing[a[pos]].insert(pos);
		}
		else {
			int l, r, x;
			cin >> l >> r >> x;
			if(sing[x].lower_bound(l) != sing[x].end() && *sing[x].lower_bound(l) <= r){
				cout << *sing[x].lower_bound(l) << ' ' << *sing[x].lower_bound(l) << '\n';
			}
			else if(nei[x].lower_bound(l) != nei[x].end() && *nei[x].lower_bound(l) < r){
				cout << *nei[x].lower_bound(l) << ' ' << *nei[x].lower_bound(l) + 1 << '\n';
			}
			else cout << "-1 -1\n";
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int times = 1;
	//cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

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