Submission #376511

#	Time	Username	Problem	Language	Result	Execution time	Memory
376511		SeDunion	Birthday gift (IZhO18_treearray)	C++17	0 / 100	73 ms	117996 KiB

treearray

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 66;

vector<int>g[N];

const int LOG = 20;

int tin[N], tout[N], up[LOG][N], timer;

void dfs(int v, int p = 1) {
	tin[v] = timer++;
	up[0][v] = p; for (int i = 1 ; i < LOG ; ++ i) up[i][v] = up[i - 1][up[i - 1][v]];
	for (int to : g[v]) if (to != p) {
		dfs(to, v);
	}
	tout[v] = timer++;
}

bool upper(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (upper(a, b)) return a;
	if (upper(b, a)) return b;
	for (int i = LOG - 1 ; i >= 0 ; -- i) {
		if (!upper(up[i][a], b)) a = up[i][a];
	}
	return up[0][a];
}

int a[N];

set<int>pos1[N], pos2[N];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1 ; i < n ; ++ i) {
		int a, b;
		cin >> a >> b;
		g[a].emplace_back(b);
		g[b].emplace_back(a);
	}
	dfs(1);
	for (int i = 1 ; i <= m ; ++ i) {
		cin >> a[i];
		pos1[a[i]].insert(i);
		if (i > 1) {
			pos2[lca(a[i], a[i - 1])].insert(i);
		}
	}
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int i, v;
			cin >> i >> v;
			pos1[a[i]].erase(i);
			if (i > 1)
				pos2[lca(a[i], a[i - 1])].erase(i);
			if (i < n)
				pos2[lca(a[i], a[i + 1])].erase(i + 1);
			a[i] = v;
			pos1[a[i]].insert(i);
			if (i > 1)
				pos2[lca(a[i], a[i - 1])].insert(i);
			if (i < n)
				pos2[lca(a[i], a[i + 1])].insert(i + 1);
			continue;
		}
		int l, r, v;
		cin >> l >> r >> v;
		{
			auto it = pos1[v].lower_bound(l);
			if (pos1[v].end() != it && *it <= r) {
				cout << *it << " " << *it << "\n";
				continue;
			}
		}
		{
			auto it = pos2[v].upper_bound(l);
			if (pos2[v].end() != it && *it <= r) {
				cout << *it - 1 << " " << *it << "\n";
				continue;
			}
		}
		cout << "-1 -1";
	}
}

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