제출 #1220975

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220975		boclobanchat	Birthday gift (IZhO18_treearray)	C++20	100 / 100	865 ms	70268 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
set< pair<int,int> > st[MAXN];
int sp[MAXN][20],dis[MAXN],A[MAXN];
vector<int> ds[MAXN];
void dfs(int i,int pre)
{
	sp[i][0]=pre;
	for(int j=1;j<=18;j++) sp[i][j]=sp[sp[i][j-1]][j-1];
	for(auto v:ds[i]) if(v!=pre)
	{
		dis[v]=dis[i]+1;
		dfs(v,i);
	}
}
int lca(int a,int b)
{
	int x=dis[a],y=dis[b],m=min(x,y);
	for(int i=18;i+1;i--)
	{
		if((x-m)&(1<<i)) a=sp[a][i];
		if((y-m)&(1<<i)) b=sp[b][i];
	}
	if(a==b) return a;
	for(int i=18;i+1;i--) if(sp[a][i]!=sp[b][i]) a=sp[a][i],b=sp[b][i];
	return sp[a][0];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<n;i++)
    {
    	int l,r;
    	cin>>l>>r;
    	ds[l].push_back(r),ds[r].push_back(l);
	}
	dfs(1,1);
	for(int i=1;i<=m;i++)
	{
		cin>>A[i];
		st[A[i]].insert({i,i});
		if(i>1) st[lca(A[i],A[i-1])].insert({i-1,i});
	}
	for(int i=1;i<=q;i++)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int p,v;
			cin>>p>>v;
			st[A[p]].erase({p,p});
			if(p>1) st[lca(A[p-1],A[p])].erase({p-1,p});
			if(p<m) st[lca(A[p],A[p+1])].erase({p,p+1});
			A[p]=v;
			st[A[p]].insert({p,p});
			if(p>1) st[lca(A[p-1],A[p])].insert({p-1,p});
			if(p<m) st[lca(A[p],A[p+1])].insert({p,p+1});
		}
		else
		{
			int l,r,v;
			cin>>l>>r>>v;
			auto ans=st[v].lower_bound({l,l});
			if(ans!=st[v].end()&&(*ans).second<=r) cout<<(*ans).first<<" "<<(*ans).second<<"\n";
			else cout<<"-1 -1\n";
		}
	}
}

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