Submission #882656

#	Time	Username	Problem	Language	Result	Execution time	Memory
882656		NintsiChkhaidze	Birthday gift (IZhO18_treearray)	C++17	100 / 100	1341 ms	83244 KiB

treearray

#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long
#define pb push_back
#define pii pair <int,int>
using namespace std;

const int N = 2e5 + 5;
int dp[N],d[25][N],arr[N];
vector <int> v[N];
multiset <int> vec[N],st[N];

void dfs(int x,int par){
	d[0][x] = par;
	dp[x] = dp[par] + 1;
	for (int to: v[x])
		if (to != par) dfs(to,x);
}

int lca(int x,int y){
	if (dp[x] < dp[y]) swap(x,y);
	for (int i = 18; i >= 0; i--)
		if (dp[d[i][x]] >= dp[y]) x = d[i][x];

	if (x == y) return x;
	for (int i = 18; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x], y = d[i][y];

	return d[0][x];
}

void upd(int idx,int p){
	int x = arr[idx],y = arr[idx + 1];
	int c = lca(x,y);

	if (!p) vec[c].erase(vec[c].find(idx));
	else vec[c].insert(idx);
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m,q;
	cin>>n>>m>>q;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}

	for (int i = 1; i <= m; i++)
		cin >> arr[i],st[arr[i]].insert(i);

	dfs(1,1);
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			d[j][i] = d[j - 1][d[j - 1][i]];

	for (int i = 1; i < m; i++){
		int c = lca(arr[i],arr[i + 1]);
		vec[c].insert(i);
	}

	while (q--){
		int tp;
		cin>>tp;

		if (tp == 1){
			int pos,val;
			cin>>pos>>val;

			st[arr[pos]].erase(st[arr[pos]].find(pos));
			st[val].insert(pos);

			if (pos - 1 >= 1 && pos - 1 < m) upd(pos-1,0);
			if (pos >= 1 && pos < m) upd(pos,0);

			arr[pos] = val;
			
			if (pos - 1 >= 1 && pos - 1 < m) upd(pos-1,1);
			if (pos >= 1 && pos < m) upd(pos,1);
		}else{
			int l,r,x;
			cin>>l>>r>>x;

			multiset <int> :: iterator it;
			if (st[x].size()){
				it = st[x].lower_bound(l);
				if (it != st[x].end() && (*it) <= r){
					cout<<(*it)<<" "<<(*it)<<endl;
					continue;
				}
			}

			if (vec[x].size()){
				it = vec[x].lower_bound(l);
				if (it != vec[x].end() && (*it) < r){
					cout<<*it<<" "<<(*it) + 1<<endl;
					continue;
				}
			}
			cout<<-1<<" "<<-1<<endl;
		}
	}
}

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