Submission #379662

#	Time	Username	Problem	Language	Result	Execution time	Memory
379662		Kevin_Zhang_TW	Birthday gift (IZhO18_treearray)	C++17	100 / 100	2334 ms	107092 KiB

treearray

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010, MAX_K = 18;

int n, m, q;
vector<int> edge[MAX_N];

int a[MAX_N];

set<int> two[MAX_N], one[MAX_N];

int anc[MAX_K][MAX_N], in[MAX_N], out[MAX_N];

bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }

void dfs(int x, int lst) {
	static int t;
	in[x] = t++;
	anc[0][x] = lst;
	for (int u : edge[x]) if (u != lst)
		dfs(u, x);
	out[x] = t;
}

void initlca() {
	dfs(1, 1);
	for (int d = 1;d < MAX_K;++d)
		for (int i = 1;i <= n;++i)
			anc[d][i] = anc[d-1][anc[d-1][i]];
}

bool inr(int ind) { return ind >= 1 && ind <= n; }

int lca(int a, int b) {
	for (int d = MAX_K - 1;d >= 0;--d)
		if (!isanc(anc[d][a], b)) a = anc[d][a];
	return isanc(a, b) ? a : anc[0][a];
}

void chg(int ind, int d) {
	if (ind == 0) return;
	int la = lca(a[ind], a[ind+1]), lb = a[ind];
	if (d == 1) {
		two[la].insert(ind);
		one[lb].insert(ind);
	}
	else {
		two[la].erase(ind);
		one[lb].erase(ind);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q;
	for (int a, b, i = 1;i < n;++i) {
		cin >> a >> b;
		edge[a].pb(b), edge[b].pb(a);
	}
	for (int i = 1;i <= m;++i)
		cin >> a[i];

	a[m+1] = 1;

	initlca();

	for (int i = 1;i <= m;++i)
		chg(i, 1);

	for (int i = 1;i <= m;++i)
		two[i].insert(m+1), one[i].insert(m+1);

	for (int t, l, r, v, pos, i = 0;i < q;++i) {
		cin >> t;
		if (t == 1) {
			cin >> pos >> v;
			chg(pos-1, -1), chg(pos, -1);
			
			a[pos] = v;

			chg(pos-1, 1), chg(pos, 1);
		}
		if (t == 2) {
			cin >> l >> r >> v;
			int p = *two[v].lower_bound(l);
			int q = *one[v].lower_bound(l);
			if (q <= r) {
				cout << q << ' ' << q << '\n';
			}
			else if (p < r)
				cout << p << ' ' << p+1 << '\n';
			else
				cout << "-1 -1\n";
		}
	}

}

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