제출 #1298342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298342		nguyenletrung	Birthday gift (IZhO18_treearray)	C++20	100 / 100	1050 ms	150224 KiB

treearray

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define ins insert
#define pb push_back
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define int ll
using namespace std;
int n,m,nq;
int a[200005],dep[200005],lca[20][200005];
vector<int> adj[200005];

set<int> t1[800005],t2[800005];

void dfs(int u,int par)
{
	for(auto v:adj[u])
	{
		if(v==par) continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
		lca[0][v]=u;
	}
}

void buildd()
{
	foru(i,1,17)
	{
		foru(j,1,n)
		{
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

int getlca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	
	ford(i,17,0)
	{
		if(dep[lca[i][u]]>=dep[v])
		{
			u=lca[i][u];
		}
	}
	
	if(v==u) return u;
	else
	{
		ford(i,17,0)
		{
			if(lca[i][u]!=lca[i][v])
			{
				u=lca[i][u];
				v=lca[i][v];
			}
		}
		return lca[0][u];
	}
	
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m>>nq;
	
	foru(i,1,n-1)
	{
		int x,y;
		cin>>x>>y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	
	dep[1]=1;
	dfs(1,0);
	buildd();
	
	foru(i,1,m) 
	{
		cin>>a[i];
		t1[a[i]].insert(i);		
	}
	
	foru(i,1,m-1)
	{
		int u=getlca(a[i],a[i+1]);
		t2[u].insert(i);
//		cout<<'?'<<u<<' '<<i<<endl;
	}
	
	while(nq--)
	{
		int ord;
		cin>>ord;
		if(ord==1)
		{
			int id,x;
			cin>>id>>x;
			
			t1[a[id]].erase(id);
			
			int par=0;
			
			par=getlca(a[id-1],a[id]);
			if(t2[par].find(id-1)!=t2[par].end())
			t2[par].erase(t2[par].find(id-1));
			
			par=getlca(a[id],a[id+1]);
			if(t2[par].find(id)!=t2[par].end())
			t2[par].erase(t2[par].find(id));
			
			a[id]=x;
			t1[a[id]].insert(id);
			
			par=getlca(a[id-1],a[id]);
			if(id-1!=0&&id!=m)
			t2[par].insert(id-1);
			
			par=getlca(a[id],a[id+1]);
			if(id!=m&&id!=0)
			t2[par].insert(id);
		}
		else
		{
			int l,r,v;
			cin>>l>>r>>v;
			
			auto it=t1[v].lower_bound(l);
			
			if(it!=t1[v].end()&&(*it)<=r)
			{
				cout<<*it<<' '<<*it<<'\n';
				continue;
			}
			
			auto itt=t2[v].lower_bound(l);
			
			if(itt!=t2[v].end()&&(*itt)<r)
			{
				cout<<*itt<<' '<<*itt+1<<'\n';
				continue;
			}
			
			cout<<-1<<' '<<-1<<'\n';
		}
	}
	
	
	
}
/*
em thi cho du co khoc
cung se den ngay phai quen
thien duong van cho ngay em den
*/

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