제출 #1100179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100179		vjudge1	Birthday gift (IZhO18_treearray)	C++17	100 / 100	789 ms	134220 KiB

treearray

//UNSTOPPABLE
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int,int>
#define tpii pair <pair <int,int> , int>
#define bruh cout << "NO\n"
using namespace std;
using namespace __gnu_pbds;
const int N = 3e5 + 5;
int mod = 1e9 + 7;
const int INF = 1e18;
int n,m,q,a[N],up[21][N],tin[N],tout[N],timer;
vector <int> g[N];
void dfs(int v , int p = 0){
	tin[v] = ++timer;
	up[0][v] = p;
	for(int i = 1 ; i <= 20 ; i++){
		up[i][v] = up[i - 1][up[i - 1][v]];
	}
	for(auto to : g[v]){
		if(to == p) continue;
		dfs(to , v);
	}
	tout[v] = timer;
}
bool upper(int a , int b){
	return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int lca(int a , int b){
	if(upper(a , b)) return a;
	if(upper(b , a)) return b;
	for(int i = 20 ; i >= 0 ; i--){
		if(!up[i][a]) continue;
		if(!upper(up[i][a] , b)) a = up[i][a];
	}
	return up[0][a];
}
set <int> st[N] , st1[N];
void Goldik(){
	cin >> n >> m >> q;
	for(int i = 1 ; i < n ; i++){
		int u,v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1);
	for(int i = 1 ; i <= m ; i++){
		cin >> a[i];
	}
	for(int i = 1 ; i <= m ; i++){
		if(i < m) st[lca(a[i] , a[i + 1])].insert(i);
		st1[a[i]].insert(i);
	}
	for(int i = 1 ; i <= q ; i++){
		int tp;
		cin >> tp;
		if(tp == 1){
			int pos,x;
			cin >> pos >> x;
			if(pos < m){
				int lc = lca(a[pos] , a[pos + 1]);
				st[lc].erase(st[lc].find(pos));
			}
			if(pos > 1){
				int lc = lca(a[pos - 1] , a[pos]);
				st[lc].erase(st[lc].find(pos - 1));
			}
			st1[a[pos]].erase(st1[a[pos]].find(pos));
			a[pos] = x;
			if(pos < m){
				int lc = lca(a[pos] , a[pos + 1]);
				st[lc].insert(pos);
			}
			if(pos > 1){
				int lc = lca(a[pos - 1] , a[pos]);
				st[lc].insert(pos - 1);
			}
			st1[a[pos]].insert(pos);
		}
		else{
			int l,r,v;
			cin >> l >> r >> v;
			if(st1[v].size()){
				auto it = st1[v].lower_bound(l);
				if(it != st1[v].end() && (*it) >= l && (*it) <= r){
					cout << (*it) << ' ' << (*it) << '\n';
					continue;
				}
			}
			if(st[v].size()){
				auto it = st[v].lower_bound(l);
				if(it != st[v].end() && (*it) >= l && (*it) < r){
					cout << (*it) << ' ' << (*it) + 1 << '\n';
					continue;
				}
			}
			cout << "-1 -1\n";
		}
	}
}
//rewai mnogo zadach vozmozhno odna iz nih gde to popadetsya
//returning winter prime?
//chem prowe tem luchshe
signed main(/*AZ AZDAN UZDIKSIZ*/){
	//freopen("txt.in","r",stdin);
	//freopen("txt.out","w",stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	srand(time(0));
	int TT = 1;
	// cin >> TT;
	for(int i = 1 ; i <= TT ; i++){
		//cout << "Case " << i << ": ";
		Goldik();
	}
}

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