Submission #1118068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118068		nikolashami	Birthday gift (IZhO18_treearray)	C++17	100 / 100	612 ms	84808 KiB

treearray

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

const int N=2e5+4,LG=ceil(log2(N))+1;
vector<int>adj[N];
int cale[LG][N],tin[N],tout[N],ti;
int n,m,q,a[N],b[N];

void dfs(int u,int p=0){
	cale[0][u]=p;
  	for(int i=1;i<LG;++i) 
  		cale[i][u]=cale[i-1][cale[i-1][u]];
  	tin[u]=ti++;
  	for(int v:adj[u]){
  	  	if(v^p)
   			dfs(v,u);
  	}
  	tout[u]=ti++;
}

bool iznad(int u,int v){
	return tout[v]<=tout[u]&&tin[v]>=tin[u];
}

int lca(int u,int v){
	if(iznad(u,v))return u;
	if(iznad(v,u))return v;
	for(int i=LG-1;i>=0;--i){
    	if(!iznad(cale[i][v],u)&&cale[i][v])
    		v=cale[i][v];
  	}
  	return cale[0][v];
}

set<int>idA[N],idB[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>m>>q;

    for(int i=1,u,v;i<n;++i){
    	cin>>u>>v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }

    tin[0]=-1e9;
    tout[0]=1e9;
    dfs(1);

    for(int i=1;i<=m;++i)
    	cin>>a[i];

    for(int i=1;i<m;++i)
    	b[i]=lca(a[i],a[i+1]);

    for(int i=1;i<=m;++i){
    	idA[a[i]].insert(i);
    	if(i<m)idB[b[i]].insert(i);
    }

    while(q--){
    	int tp;
    	cin>>tp;
    	if(tp==2){
    		int l,r,x;
    		cin>>l>>r>>x;
    		auto it1=idA[x].lower_bound(l);
    		auto it2=idB[x].lower_bound(l);
    		if(it1!=idA[x].end()&&*it1<=r)
    			cout<<*it1<<' '<<*it1<<'\n';
    		else if(it2!=idB[x].end()&&*it2<r)
    			cout<<*it2<<' '<<*it2+1<<'\n';
    		else
    			cout<<-1<<' '<<-1<<'\n';
    	}else{
    		int id,x;
    		cin>>id>>x;
    		idA[a[id]].erase(id);
    		a[id]=x;
    		idA[a[id]].insert(id);
    		if(id+1<=m){
    			idB[b[id]].erase(id);
    			b[id]=lca(a[id],a[id+1]);
    			idB[b[id]].insert(id);
    		}
    		if(id-1>=1){
    			idB[b[id-1]].erase(id-1);
    			b[id-1]=lca(a[id],a[id-1]);
    			idB[b[id-1]].insert(id-1);
    		}
    	}
    }
}

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