제출 #545691

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
545691		dostigator	Birthday gift (IZhO18_treearray)	C++17	0 / 100	15 ms	24032 KiB

treearray

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

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
*/

#define all(a) a.begin(),a.end()
#define vt vector
#define pb push_back
#define endl '\n'
#define Y second
#define X first
typedef long long ll;
typedef long double ld;
const ll mod=1e9+7;
const ll INF=1e18;
const int inf=1e9;
const int N=2e5+777;
const int M=2e3;

vt<int>g[N];
set<int>pos1[N],pos2[N];
int a[N],b[N],n,m,q,tin[N],tout[N],tim,up[30][N];

void dfs(int x,int pr){
	tin[x]=tim++;
	up[0][x]=pr;
	for(int i=1; i<20; ++i) up[i][x]=up[i-1][up[i-1][x]];
	for(int to:g[x]) if(to!=pr){
		dfs(to,x);
	}tout[x]=tim++;
}

bool isparent(int lol,int kek){
	return (tin[lol]<=tin[kek] && tout[kek]<=tout[lol]);
}

int lca(int lol,int kek){
	if(isparent(lol,kek))return lol;
	if(isparent(kek,lol))return kek;
	for(int i=19;i>=0;--i)if(!isparent(up[i][lol],kek))lol=up[i][lol];
	return up[0][lol];
}

void solve(){
	cin>>n>>m>>q;
	while(--n){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1,1);
	for(int i=1; i<=m; ++i){
		cin>>a[i];
		pos1[a[i]].insert(i);
		if(i>1){
			b[i]=lca(a[i],a[i-1]);
			pos2[b[i]].insert(i);
		}
	}
	for(int i=1; i<=q; ++i){
		int tp;
		cin>>tp;
		if(tp==2){
			int l,r,v;
			cin>>l>>r>>v;
			if(pos1[v].empty() || *pos1[v].rbegin()<l){}
			else {
				int h=*pos1[v].lower_bound(l);
				if(h<=r){
					cout<<h<<' '<<h<<endl;
					continue;
				}
			}
			if(pos2[v].empty() || *pos2[v].rbegin()<=l){}
			else {
				int h=*pos2[v].upper_bound(l);
				if(h<=r){
					cout<<h-1<<' '<<h<<endl;
					continue;
				}
			}
			cout<<-1<<' '<<-1<<endl;
			continue;
		}
		int pos,v;
		cin>>pos>>v;
		pos1[a[pos]].erase(pos);
		pos1[v].insert(pos);
		if(pos>1)pos2[b[pos]].erase(pos);
		if(pos<n)pos2[b[pos+1]].erase(pos+1);
		a[pos]=v;
		if(pos>1)pos2[lca(a[pos],a[pos-1])].insert(pos);
		if(pos<n)pos2[lca(a[pos],a[pos+1])].insert(pos+1);
		if(pos>1) b[pos]=lca(a[pos],a[pos-1]);
		if(pos<n)b[pos+1]=lca(a[pos+1],a[pos]);
	}
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll tt=1;
    //cin>>tt;
    while(tt--)solve();
}

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