Submission #41544

#	Time	Username	Problem	Language	Result	Execution time	Memory
41544		aome	Birthday gift (IZhO18_treearray)	C++14	0 / 100	71 ms	80376 KiB

treearray

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

typedef pair<int, int> ii;

struct SegmentTree {
	int a[N];
	set<ii> it[4 * N];

	void build(int i, int l, int r) {
		for (int j = l; j <= r; ++j) it[i].insert(ii(a[j], j));
		if (l == r) return;
		int mid = (l + r) >> 1;
		build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	} 

	void init(int n, int a[]) {
		for (int i = 1; i <= n; ++i) this -> a[i] = a[i];
		build(1, 1, n);
	}

	void upd(int i, int l, int r, ii x, bool type) {
		if (type == 0) it[i].insert(x);
		if (type == 1) it[i].erase(x);
		if (l == r) return;
		int mid = (l + r) >> 1;
		if (mid >= x.second) upd(i << 1, l, mid, x, type);
		else upd(i << 1 | 1, mid + 1, r, x, type);
	}

	int find(int i, int l, int r, int L, int R, int x) {
		if (l > L || L > r) return 0;
		if (L <= l && r <= R) {
			auto j = it[i].lower_bound(ii(x, 0));
			if (j != it[i].end() && j -> first == x) return j -> second;
			return 0;
		}
		int mid = (l + r) >> 1;
		return max(find(i << 1, l, mid, L, R, x), find(i << 1 | 1, mid + 1, r, L, R, x));
	}
} IT1, IT2;

int n, m, q;
int a[N];
int b[N];
int high[N];
int p[20][N];
vector<int> G[N];

int lca(int u, int v) {
	if (high[u] > high[v]) swap(u, v);
	for (int i = 18; i >= 0; --i) {
		if (high[p[i][v]] >= high[u]) v = p[i][v];
	}
	for (int i = 18; i >= 0; --i) {
		if (p[i][v] != p[i][u]) v = p[i][v], u = p[i][u];
	}
	return (u == v) ? u : p[0][u];
}

void dfs(int u) {
	for (auto v : G[u]) {
		if (p[0][u] == v) continue;
		p[0][v] = u, high[v] = high[u] + 1, dfs(v);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i < n; ++i) {
		int u, v; cin >> u >> v;
		G[u].push_back(v), G[v].push_back(u);
	}
	p[0][1] = 1, dfs(1);
	for (int i = 1; i <= 18; ++i) {
		for (int j = 1; j <= n; ++j) {
			p[i][j] = p[i - 1][p[i - 1][j]];
		}
	}
	for (int i = 1; i <= m; ++i) cin >> a[i];
	IT1.init(m, a);
	for (int i = 1; i < m; ++i) b[i] = lca(a[i], a[i + 1]);
	IT2.init(m - 1, b);
	while (q--) {
		int type; cin >> type;
		if (type == 1) {
			int pos, v; cin >> pos >> v;
			IT1.upd(1, 1, m, ii(a[pos], pos), 1);
			IT1.upd(1, 1, m, ii(v, pos), 0);
			IT2.upd(1, 1, m - 1, ii(lca(a[pos - 1], a[pos]), pos - 1), 1);
			IT2.upd(1, 1, m - 1, ii(lca(a[pos], a[pos + 1]), pos), 1);
			IT2.upd(1, 1, m - 1, ii(lca(a[pos - 1], v), pos - 1), 1);
			IT2.upd(1, 1, m - 1, ii(lca(v, a[pos + 1]), pos), 1);
			a[pos] = v;
		}
		else {
			int l, r, v; cin >> l >> r >> v;
			int res = 0;
			res = IT1.find(1, 1, m, l, r, v);
			if (!res) {
				res = IT2.find(1, 1, m - 1, l, r - 1, v);
				if (res) {
					cout << res << ' ' << res + 1 << '\n'; continue;
				}
			}
			else {
				cout << res << ' ' << res << '\n'; continue;
			}
			cout << "-1 -1\n";
		}
	}
}

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