제출 #341957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
341957		Tosic	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1222 ms	77420 KiB

treearray

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

int n, m, q;
int up[maxn][20],iT[maxn], oT[maxn], gT, a[maxn];
vector<vector<int> > gr;
set<int> allNum[maxn], allPai[maxn];

void dfs(int x, int p){
	iT[x] = gT;
	++gT;
	up[x][0] = p;
	for(int i =1 ; i < 20; ++i){
		up[x][i] = up[up[x][i-1]][i-1];
	}
	for(auto i : gr[x]){
		if(i != p){
			dfs(i, x);
		}
	}
	oT[x] = gT;
	++gT;
}

bool isA(int a, int b){
	if(iT[a] <= iT[b] and oT[a] >= oT[b]){
		return true;
	}
	return 0;
}

int lca(int x, int y){
	if(isA(x, y)){
		return x;
	}
	if(isA(y, x)){
		return y;
	}
	for(int i = 19; i >= 0; --i){
		if(!isA(up[x][i], y)){
			x = up[x][i];
		}
	}
	return up[x][0];
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	cin >> n >> m >> q;
	gr.resize(n, vector<int>());
	for(int i = 1; i < n; ++i){
		int u,v;
		cin >> u >> v;
		--u, v--;
		gr[u].push_back(v);
		gr[v].push_back(u);
	}
	dfs(0, 0);
	for(int i = 0; i < m; ++i){
		cin >> a[i];
		--a[i];
		allNum[a[i]].insert(i);
		if(i){
			allPai[lca(a[i], a[i-1])].insert(i);
		}
	}
	for(int i = 0; i < q; ++i){
		int t;
		cin >> t;
		if(t == 1){
			int ps, val;
			cin >> ps >> val;
			--ps;
			--val;
			allNum[a[ps]].erase(ps);
			if(ps){
				allPai[lca(a[ps-1], a[ps])].erase(ps);
				allPai[lca(a[ps-1], val)].insert(ps);
			}
			if(ps < m-1){
				allPai[lca(a[ps+1], a[ps])].erase(ps+1);
				allPai[lca(a[ps+1], val)].insert(ps+1);
			}
			a[ps] = val;
			allNum[val].insert(ps);
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			--l, --r, --v;
			auto tmp = allNum[v].lower_bound(l);
			if(tmp != allNum[v].end() and *tmp <= r){
				cout << *tmp+1 << ' ' << *tmp+1 << '\n';
				continue;
			}
			tmp=allPai[v].upper_bound(l);
			if(tmp != allPai[v].end() and *tmp <= r){
				cout << *tmp << ' ' << *tmp+1<<'\n';
				continue;
			}
			cout <<"-1 -1\n";
		}
	}
}

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