Submission #1183230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183230		PieArmy	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1272 ms	68768 KiB

treearray

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
using namespace std;

int n,m,q;
vector<int>komsu[200023];
int arr[200023];
int par[200023][18],dep[200023];
set<pair<int,int>>loc[200023];

void dfs(int pos){
	for(int i=1;i<18;i++){
		par[pos][i]=par[par[pos][i-1]][i-1];
	}
	for(int x:komsu[pos]){
		if(x==par[pos][0])continue;
		dep[x]=dep[pos]+1;
		par[x][0]=pos;
		dfs(x);
	}
}

int lca(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	for(int i=0;i<18;i++){
		if((1<<i)&(dep[a]-dep[b])){
			a=par[a][i];
		}
	}
	if(a==b)return a;
	for(int i=18-1;i>=0;i--){
		if(par[a][i]!=par[b][i]){
			a=par[a][i];
			b=par[b][i];
		}
	}
	return par[a][0];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>m>>q;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		komsu[x].pb(y);
		komsu[y].pb(x);
	}
	for(int i=1;i<=m;i++){
		cin>>arr[i];
	}
	dfs(1);
	for(int i=0;i<=m;i++){
		loc[arr[i]].insert({i,i});
		int lc=lca(arr[i],arr[i+1]);
		loc[lc].insert({i,i+1});
	}
	while(q--){
		int c;cin>>c;
		if(c==1){
			int tar,v;cin>>tar>>v;
			loc[arr[tar]].erase({tar,tar});
			int lc=lca(arr[tar-1],arr[tar]);
			loc[lc].erase({tar-1,tar});
			lc=lca(arr[tar],arr[tar+1]);
			loc[lc].erase({tar,tar+1});
			arr[tar]=v;
			loc[arr[tar]].insert({tar,tar});
			lc=lca(arr[tar-1],arr[tar]);
			loc[lc].insert({tar-1,tar});
			lc=lca(arr[tar],arr[tar+1]);
			loc[lc].insert({tar,tar+1});
		}
		else{
			int l,r,v;cin>>l>>r>>v;
			auto itr=loc[v].lower_bound({l,l});
			if(itr==loc[v].end()){
				cout<<"-1 -1\n";
				continue;
			}
			if(itr->sc>r){
				cout<<"-1 -1\n";
				continue;
			}
			cout<<itr->fr<<" "<<itr->sc<<endl;
		}
	}
}

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