Submission #1084316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084316		xnqs	Birthday gift (IZhO18_treearray)	C++17	100 / 100	547 ms	82568 KiB

treearray

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <set>

int gs, x, q;
std::vector<std::vector<int>> adj_list;
int arr[200005];
int up[18][200005];
int depth[200005];
std::set<int> occurences1[200005]; // occurences of node i in arr
std::set<int> occurences2[200005]; // occurences of lca of any two consecutive nodes in arr

void dfs(int k, int p) {
	depth[k] = depth[p]+1;
	up[0][k] = p;
	for (int l = 1; l < 18; l++) {
		up[l][k] = up[l-1][up[l-1][k]];
	}

	for (const auto& i : adj_list[k]) {
		if (i!=p) {
			dfs(i,k);
		}
	}
}

int get_kth_ancestor(int node, int k) {
	while (k) {
		int lvl = 31-__builtin_clz(k);
		node = up[lvl][node];
		k ^= (1<<lvl);
	}
	return node;
}

int get_lca(int a, int b) {
	if (depth[a]>depth[b]) {
		std::swap(a,b);
	}

	b = get_kth_ancestor(b,depth[b]-depth[a]);

	for (int lvl = 17; a != b;) {
		while (lvl-1>=0&&up[lvl][a]==up[lvl][b]) {
			--lvl;
		}

		a = up[lvl][a];
		b = up[lvl][b];
	}

	return a;
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> gs >> x >> q;
	adj_list.resize(gs+1);
	for (int i = 0, a, b; i < gs-1; i++) {
		std::cin >> a >> b;
		adj_list[a].emplace_back(b);
		adj_list[b].emplace_back(a);
	}

	dfs(1,0);

	for (int i = 1; i <= x; i++) {
		std::cin >> arr[i];
		occurences1[arr[i]].emplace(i);
	}
	for (int i = 1; i+1 <= x; i++) {
		occurences2[get_lca(arr[i],arr[i+1])].emplace(i);
	}

	while (q--) {
		int op;
		std::cin >> op;
		if (op==1) {
			int pos, val;
			std::cin >> pos >> val;

			occurences1[arr[pos]].erase(pos);
			if (pos-1>=1) {
				occurences2[get_lca(arr[pos-1],arr[pos])].erase(pos-1);
			}
			if (pos+1<=x) {
				occurences2[get_lca(arr[pos],arr[pos+1])].erase(pos);
			}

			arr[pos] = val;
			occurences1[arr[pos]].emplace(pos);
			if (pos-1>=1) {
				occurences2[get_lca(arr[pos-1],arr[pos])].emplace(pos-1);
			}
			if (pos+1<=x) {
				occurences2[get_lca(arr[pos],arr[pos+1])].emplace(pos);
			}
		}
		else {
			int l, r, k;
			std::cin >> l >> r >> k;

			// if k itself pops up in [l, r]
			auto it = occurences1[k].lower_bound(l);
			if (it!=occurences1[k].end()&&*it<=r) {
				std::cout << (*it) << " " << (*it) << "\n";
				continue;
			}

			// if two consecutive occurences with lca k happen in [l, r]
			it = occurences2[k].lower_bound(l);
			if (it!=occurences2[k].end()&&(*it+1)<=r) {
				std::cout << (*it) << " " << (*it+1) << "\n";
				continue;
			}

			std::cout << "-1 -1\n";
		}
	}
}

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