제출 #1252963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252963		nhq0914	Birthday gift (IZhO18_treearray)	C++17	100 / 100	771 ms	79216 KiB

treearray

#include<bits/stdc++.h>
#define F(i, a, b) for(int i = (a); i <= (b); ++i)
#define R(i, a, b) for(int i = (a); i >= (b); --i)
#define N(a)(int)a.size()
#define full(a)a.begin(),a.end()
using namespace std;
template<typename t>inline void sort(vector<t>&a){sort(full(a));}
template<typename t>inline void uni(vector<t>&a){sort(a);a.erase(unique(full(a)),a.end());}
const int data_size=1<<20;
char Data[data_size];
char rchar(){
	static int pos=0,len=0;
	if(pos==len){
		pos=0;
		len=(int)fread(Data,1,data_size,stdin);
		if(!len)return EOF;
	}
	return Data[pos++];
}
template<typename t>void read(t &x){
	x=0;
	bool neg=false;
	char c=rchar();
	if(c=='-')neg=true,c=rchar();
	for(;c>='0'&&c<='9';c=rchar())(x*=10)+=c-'0';
	if(neg)x=-x;
}
template<typename m, typename ...t>void read(m& _m, t&... _t){
	read(_m);
	read(_t...);
}
//...
const int MN=2e5+1;
int n,m,q,a[MN],h[MN],par[18][MN];
vector<int>g[MN];
set<int>single[MN],couple[MN];
void dfs(int v){
	for(int &x:g[v])if(x!=par[0][v]){
		h[x]=h[v]+1;
		par[0][x]=v;
		F(i,1,17)par[i][x]=par[i-1][par[i-1][x]];
		dfs(x);
	}
}
int lca(int u,int v){
	if(h[u]<h[v])u^=v^=u^=v;
	F(i,0,17)if((h[u]-h[v])&(1<<i))u=par[i][u];
	if(u==v)return u;
	R(i,17,0)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v];
	return par[0][u];
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	read(n,m,q);
	F(i,1,n-1){
		int u,v;read(u,v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	par[0][1]=1;
	dfs(1);
	F(i,1,m){
		read(a[i]);
		single[a[i]].insert(i);
		if(i>1)couple[lca(a[i-1],a[i])].insert(i-1);
	}
	while(q--){
		int t;read(t);
		if(t==1){
			int p,v;read(p,v);
			if(a[p]==v)continue;
			single[a[p]].erase(p);
			single[v].insert(p);
			if(p>1){
				couple[lca(a[p-1],a[p])].erase(p-1);
				couple[lca(a[p-1],v)].insert(p-1);
			}
			if(p<m){
				couple[lca(a[p],a[p+1])].erase(p);
				couple[lca(v,a[p+1])].insert(p);
			}
			a[p]=v;
		}
		else{
			int l,r,v;read(l,r,v);
			set<int>::iterator it=single[v].lower_bound(l);
			if(it!=single[v].end()&&*it<=r){cout<<*it<<' '<<*it<<'\n';continue;}
			it=couple[v].lower_bound(l);
			if(it!=couple[v].end()&&*it<r){cout<<*it<<' '<<*it+1<<'\n';continue;}
			cout<<"-1 -1\n";
		}
	}
	cerr<<"runtime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<"s\n";
	return 0;
}

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