Submission #342301

#	Time	Username	Problem	Language	Result	Execution time	Memory
342301		ogibogi2004	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1903 ms	97644 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+6;
set<int>s1[MAXN];
set<int>s2[MAXN];
vector<int>g[MAXN];
int a[MAXN],n,m,q;
int dp[MAXN][20],depth[MAXN];
void dfs(int u,int p)
{
	dp[u][0]=p;
	depth[u]=depth[p]+1;
	for(auto v:g[u])
	{
		if(v==p)continue;
		dfs(v,u);
	}
}
void precompute()
{
	for(int s=1;s<20;s++)
	{
		for(int i=1;i<=n;i++)
		{
			dp[i][s]=dp[dp[i][s-1]][s-1];
		}
	}
}
int lca(int x,int y)
{
	if(depth[x]<depth[y])swap(x,y);
	int diff=depth[x]-depth[y];
	for(int i=0;i<20;i++)
	{
		if(diff&(1<<i))
		{
			x=dp[x][i];
		}
	}
	if(x==y)return x;
	for(int i=19;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i];
			y=dp[y][i];
		}
	}
	return dp[x][0];
}
int main()
{
	cin>>n>>m>>q;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	precompute();
	for(int i=1;i<=n;i++)
	{
		s1[i].insert(MAXN);
		s2[i].insert(MAXN);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		s1[a[i]].insert(i);
	}
	for(int i=1;i<m;i++)
	{
		s2[lca(a[i],a[i+1])].insert(i);
	}
	for(int i=1;i<=q;i++)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			int v,pos;
			cin>>pos>>v;
			if(pos!=m)
			{
				s2[lca(a[pos],a[pos+1])].erase(pos);
			}
			if(pos!=1)
			{
				s2[lca(a[pos-1],a[pos])].erase(pos-1);
			}
			s1[a[pos]].erase(pos);
			a[pos]=v;
			if(pos!=m)
			{
				s2[lca(a[pos],a[pos+1])].insert(pos);
			}
			if(pos!=1)
			{
				s2[lca(a[pos-1],a[pos])].insert(pos-1);
			}
			s1[a[pos]].insert(pos);
		}
		else
		{
			int l,r,v;
			cin>>l>>r>>v;
			int xd=(*s1[v].lower_bound(l));
			if(xd<=r)
			{
				cout<<xd<<" "<<xd<<endl;
				continue;
			}
			xd=(*s2[v].lower_bound(l));
			if(xd<r)
			{
				cout<<xd<<" "<<xd+1<<endl;
				continue;
			}
			cout<<"-1 -1\n";
		}
	}
return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

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