제출 #887386

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887386		pcc	Birthday gift (IZhO18_treearray)	C++14	100 / 100	906 ms	80980 KiB

treearray

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

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define mid ((l+r)>>1)

const int mxn = 2e5+10;
int n,m,q;
pii dfn[mxn];
int par[mxn][20];
int dep[mxn];
vector<int> tree[mxn];
int arr[mxn];
int ppp = 0;
set<pii> ap[mxn];

void dfs(int now){
	for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
	for(auto nxt:tree[now]){
		if(nxt == par[now][0])continue;
		dep[nxt] = dep[now]+1;
		par[nxt][0] = now;
		dfs(nxt);
	}
	return;
}

int anc(int a,int b){
	if(dep[a]<dep[b])swap(a,b);
	int d = dep[a]-dep[b];
	for(int i = 19;i>=0;i--){
		if(d&(1<<i))a = par[a][i];
	}
	for(int i = 19;i>=0;i--){
		if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
	}
	return a==b?a:par[a][0];
}

void build(){
	for(int i = 1;i<=m;i++){
		ap[arr[i]].insert({i,i});
	}
	for(int i = 2;i<=m;i++){
		ap[anc(arr[i-1],arr[i])].insert({i-1,i});
	}
	return;
}

void modify(int p,int v){
	ap[arr[p]].erase({p,p});
	if(p>1)ap[anc(arr[p-1],arr[p])].erase({p-1,p});
	if(p<m)ap[anc(arr[p],arr[p+1])].erase({p,p+1});
	arr[p] = v;
	ap[arr[p]].insert({p,p});
	if(p>1)ap[anc(arr[p-1],arr[p])].insert({p-1,p});
	if(p<m)ap[anc(arr[p],arr[p+1])].insert({p,p+1});
	return;
}
pii getval(int l,int r,int tar){
	auto it = ap[tar].lower_bound({l,-1});
	if(it == ap[tar].end()||it->sc>r)return {-1,-1};
	else return *it;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m>>q;
	for(int i = 1;i<n;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 1;i<=m;i++){
		cin>>arr[i];
	}
	par[1][0] = 1;
	dfs(1);
	build();
	//for(auto &i:segtree[0])cout<<i.fs<<' '<<i.sc.fs<<','<<i.sc.sc<<';';
	while(q--){
		int tp;
		cin>>tp;
		if(tp == 1){
			int p,v;
			cin>>p>>v;
			modify(p,v);
		}
		else{
			int l,r,v;
			cin>>l>>r>>v;
			auto re = getval(l,r,v);
			cout<<re.fs<<' '<<re.sc<<'\n';
		}
	}
	return 0;
}

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