Submission #336303

#	Time	Username	Problem	Language	Result	Execution time	Memory
336303		super_j6	Birthday gift (IZhO18_treearray)	C++14	100 / 100	2054 ms	69740 KiB

treearray

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 200000, k = __lg(mxn - 1) + 1;
int n, m, q;
int a[mxn], lc[mxn], d[mxn];
int p[k][mxn];
vector<int> g[mxn];
set<pi> s[mxn];

void dfs(int c){
	for(int i = 1; i < k; i++) p[i][c] = ~p[i - 1][c] ? p[i - 1][p[i - 1][c]] : -1;
	for(int i : g[c]) if(i != p[0][c]) d[i] = d[c] + 1, p[0][i] = c, dfs(i);
}

int lca(int x, int y){
	if(d[x] < d[y]) swap(x, y);
	for(int i = k - 1; ~i; i--) if(~p[i][x] && d[p[i][x]] >= d[y]) x = p[i][x];
	for(int i = k - 1; ~i; i--) if(p[i][x] != p[i][y]) x = p[i][x], y = p[i][y];
	return x == y ? x : p[0][x];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> q;
	
	for(int i = 0; i < n - 1; i++){
		int u, v;
		cin >> u >> v;
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	
	p[0][0] = -1;
	dfs(0);
	
	for(int i = 0; i < m; i++){
		cin >> a[i];
		s[--a[i]].insert({i, i});
		if(i) s[lc[i - 1] = lca(a[i - 1], a[i])].insert({i - 1, i});
	} 
	
	while(q--){
		int t;
		cin >> t;
		if(t & 1){
			int x, y;
			cin >> x >> y;
			x--, y--;
			s[a[x]].erase({x, x});
			if(x) s[lc[x - 1]].erase({x - 1, x});
			if(x < m - 1) s[lc[x]].erase({x, x + 1});
			
			s[a[x] = y].insert({x, x});
			if(x) s[lc[x - 1] = lca(a[x - 1], a[x])].insert({x - 1, x});
			if(x < m - 1) s[lc[x] = lca(a[x], a[x + 1])].insert({x, x + 1});
		}else{
			int l, r, x;
			cin >> l >> r >> x;
			l--, r--, x--;
			auto it = s[x].lower_bound({l, l});
			pi p = it != s[x].end() && it->s <= r ? *it : pi{-2, -2};
			cout << p.f + 1 << " " << p.s + 1 << endl;
		}
	}

	return 0;
}

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