Submission #379420

#	Time	Username	Problem	Language	Result	Execution time	Memory
379420		cheissmart	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1168 ms	82796 KiB

treearray

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7, N = 2e5 + 7;

int a[N], l[N];
set<int> where[N], where2[N];
vi G[N];

int p[N][20], d[N];

void dfs(int u, int pa = 0, int depth = 0) {
	p[u][0] = pa;
	for(int i = 1; i < 20; i++)
		p[u][i] = p[p[u][i - 1]][i - 1];
	d[u] = depth;
	for(int v:G[u]) if(v != pa)
		dfs(v, u, depth + 1);
}

int lca(int u, int v) {
	if(d[u] > d[v]) swap(u, v);
	for(int i = 19; i >= 0; i--)
		if((d[v] - d[u]) >> i & 1)
			v = p[v][i];
	if(u == v) return u;
	for(int i = 19; i >= 0; i--)
		if(p[u][i] != p[v][i])
			u = p[u][i], v = p[v][i];
	return p[u][0];
}

signed main()
{
	IO_OP;
	
	int n, m, q;
	cin >> n >> m >> q;
	for(int i = 0; i < n - 1; 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];
		where2[a[i]].insert(i);
	}
	auto del = [&] (int pos) {
		where[l[pos]].erase(pos);
	};
	auto calc = [&] (int pos) {
		l[pos] = lca(a[pos], a[pos + 1]);
		where[l[pos]].insert(pos);
	};
	for(int i = 1; i < m; i++) calc(i);
	while(q--) {
		int op;
		cin >> op;
		if(op == 1) {
			int pos, v;
			cin >> pos >> v;
			where2[a[pos]].erase(pos);
			a[pos] = v;
			where2[a[pos]].insert(pos);
			if(pos - 1 >= 1) {
				del(pos - 1);
				calc(pos - 1);
			}
			if(pos + 1 <= m) {
				del(pos);
				calc(pos);
			}
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			auto it = where[v].lower_bound(l);
			if(it != where[v].end() && *it < r) {
				cout << *it << " " << *it + 1 << '\n';
			} else {
				auto it = where2[v].lower_bound(l);
				if(it != where2[v].end() && *it <= r)
					cout << *it << ' ' << *it << '\n';
				else
					cout << -1 << " " << -1 << '\n';
			}
		}
	}

}

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