Submission #342295

#	Time	Username	Problem	Language	Result	Execution time	Memory
342295		Gurban	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1133 ms	83692 KiB

treearray

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

using ll = long long;

const int maxn=2e5+5;
int n,m,q,sp[maxn][21],lg;
int x,y,a[maxn],L[maxn],tp;
int l[maxn];
vector<int>E[maxn];
set<int>s[maxn];
set<int>st[maxn];

void dfs(int nd,int pr){
	L[nd] = L[pr] + 1;
	sp[nd][0] = pr;
	for(auto i : E[nd]) if(i != pr) dfs(i,nd);
}

int lca(int a,int b){
	if(L[a] < L[b]) swap(a,b);
	for(int i = lg;i >= 0;i--)
		if(L[a] - (1<<i) >= L[b]) a = sp[a][i];
	if(a==b) return a;
	for(int i = lg;i >= 0;i--)
		if(sp[a][i] and sp[a][i] != sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> q;
	for(int i = 1;i < n;i++){
		cin >> x >> y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1,0);
	lg = __lg(n);
	for(int i = 1;i <= lg;i++) for(int j = 1;j <= n;j++) sp[j][i] = sp[sp[j][i-1]][i-1];
	for(int i = 1;i <= m;i++){
		cin >> a[i];
		if(i == 1) continue;
		int lc = lca(a[i],a[i-1]);
		l[i] = lc;
		s[lc].insert(i);
		st[a[i]].insert(i);
	}
	// for(int i = 1;i <= m;i++) cout<<l[i]<<' '; cout<<'\n';
	while(q--){
		cin >> tp;
		if(tp == 1){
			int pos,val;
			cin >> pos >> val;
			if(pos > 1){
				s[l[pos]].erase(pos);
				int lc = lca(a[pos-1],val);
				l[pos] = lc;
				s[lc].insert(pos);
			}
			if(pos < m){
				s[l[pos+1]].erase(pos + 1);
				int lc = lca(a[pos+1],val);
				l[pos + 1] = lc;
				s[lc].insert(pos + 1);
			}
			st[a[pos]].erase(pos);
			st[val].insert(pos);
			a[pos] = val;
		}
		else {
			int l,r,val;
			cin >> l >> r >> val;
			auto p = st[val].lower_bound(l);
			if(p != st[val].end() and *p <= r){cout<<*p<<' '<<*p<<'\n';continue;}
			auto t = s[val].upper_bound(l);
			if(t != s[val].end() and *t <= r){cout<<*t-1<<' '<<*t<<'\n';continue;}
			cout<<"-1 -1\n";
		}
	}
}
/*
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
*/

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