Submission #379638

#	Time	Username	Problem	Language	Result	Execution time	Memory
379638		Seanliu	Birthday gift (IZhO18_treearray)	C++14	0 / 100	19 ms	23916 KiB

treearray

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 2e5 + 326, maxLog = 17;
set<int> pos[maxN], sing[maxN];

int N, M, com, v, x, y, l, r, dep[maxN], jump[maxN], pa[maxN], Q, arr[maxN];
vector<int> adj[maxN];

void getAnc(int p = 1, int u = 1){
	pa[u] = p;
	if(u == p){
		jump[u] = p;
	} else {
		if(dep[jump[jump[p]]] - dep[jump[p]] == dep[jump[p]] - dep[p]) jump[u] = jump[jump[p]]; 
		else jump[u] = p;
	}
	for(int v : adj[u]) if(v != p) getAnc(u, v);
}

int lca(int a, int b){
	if(dep[a] > dep[b]) swap(a, b);
	while(dep[b] > dep[a]){
		if(dep[jump[b]] < dep[a]) b = pa[b];
		else b = jump[b];
	}
	if(a == b) return a;
	while(pa[a] != pa[b]){
		if(jump[a] == jump[b]){
			a = pa[a];
			b = pa[b];
		} else {
			a = jump[a];
			b = jump[b];
		}
	}
	return pa[a];
}

int main(){
	cin >> N >> M >> Q;
	for(int i = 0; i < N - 1; i++){
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	getAnc();
	for(int i = 1; i <= M; i++){
		cin >> arr[i];		
		sing[arr[i]].insert(i);
	}
	for(int i = 1; i < M; i++){
		pos[lca(arr[i], arr[i + 1])].insert(i);
		//cout << arr[i] << " " << arr[i + 1] << ": " << lca(arr[i], arr[i + 1]) << endl;
	}
	while(Q--){
		cin >> com;
		if(com == 1){
			cin >> x >> v;
			sing[arr[x]].erase(x);
			if(x + 1 <= M){
				pos[lca(arr[x], arr[x + 1])].erase(x);
			}
			if(x - 1 >= 1){
				pos[lca(arr[x - 1], arr[x])].erase(x - 1);	
			}
			arr[x] = v;
			sing[arr[x]].insert(x);
			if(x + 1 <= M){
				pos[lca(arr[x], arr[x + 1])].insert(x);
			}
			if(x - 1 >= 1){
				pos[lca(arr[x - 1], arr[x])].insert(x - 1);	
			}
		} else {
			cin >> l >> r >> v;
			auto it = sing[v].lower_bound(l);
			if(it != sing[v].end() && *it <= r){
				cout << *it << " " << *it << endl;
			} else {
				auto it2 = pos[v].lower_bound(l);
				//if(it2 != pos[v].end()) cout << "found: " << *it2 << endl;
				if(it2 != pos[v].end() && *it2 + 1 <= r){
					cout << *it2 << " " << *it2 + 1 << endl;
				} else {
					cout << "-1 -1" << endl;
				}
			}
		}
	}

}

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