Submission #174697

#	Time	Username	Problem	Language	Result	Execution time	Memory
174697		Lightning	Birthday gift (IZhO18_treearray)	C++14	100 / 100	1237 ms	84988 KiB

treearray

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll

const int N = 2e5 + 5;
const int LG = 18;

int n, m, q, a[N];
vector <int> g[N];
int up[N][20], tin[N], tout[N], timer;
set <int> st[N], hv[N];

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

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

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

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m >> q;
	for(int i = 1; i < n; ++i) {
		int p, q;
		cin >> p >> q;
		g[p].pb(q);
		g[q].pb(p);
	}
	dfs(1, 1);
	for(int i = 1; i <= m; ++i) {
		cin >> a[i];
	}
	for(int i = 1; i < m; ++i) {
		st[lca(a[i], a[i + 1])].insert(i);
	}
	for(int i = 1; i <= m; ++i) {
		hv[a[i]].insert(i);
	}
	for(int it = 1; it <= q; ++it) {
		int type;
		cin >> type;
		if(type == 1) {
			int pos, v;
			cin >> pos >> v;
			if(1 <= pos - 1) {
				st[lca(a[pos - 1], a[pos])].erase(pos - 1);
				st[lca(a[pos - 1], v)].insert(pos - 1);
			} if(pos + 1 <= m) {
				st[lca(a[pos], a[pos + 1])].erase(pos);
				st[lca(v, a[pos + 1])].insert(pos);
			}
			hv[a[pos]].erase(pos);
			hv[v].insert(pos);
			a[pos] = v;
		} else {
			int l, r, v;
			cin >> l >> r >> v;
			auto it = st[v].lower_bound(l);
			if(it != st[v].end() && *it < r) {
				cout << *it <<' '<< *it + 1 <<'\n';
				continue;
			}
			auto it2 = hv[v].lower_bound(l); 
			if(it2 != hv[v].end() && *it2 <= r) {
				cout << *it2 <<' '<< *it2 <<'\n'; 
				continue;
			} 
			cout << -1 <<' '<< -1 <<'\n';	
		} 
	}
	return 0;
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5 
2 1 3 1
*/

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