Submission #882633

#	Time	Username	Problem	Language	Result	Execution time	Memory
882633		NintsiChkhaidze	Birthday gift (IZhO18_treearray)	C++17	0 / 100	48 ms	109128 KiB

treearray

#include <bits/stdc++.h>
#define s second
#define f first
#define ll long long
#define pb push_back
#define pii pair <int,int>
#define int ll
using namespace std;

const int N = 2e5 + 5,inf = 1e18;

int dp[N],d[25][N],arr[N];
vector <int> v[N];
multiset <int> vec[N],st[N];

void dfs(int x,int par){
	d[0][x] = par;
	dp[x] = dp[par] + 1;
	for (int to: v[x]){
		if (to != par){
			dfs(to,x);
		}
	}
}

int lca(int x,int y){
	if (dp[x] < dp[y]) swap(x,y);
	for (int i = 18; i >= 0; i--)
		if (dp[d[i][x]] >= dp[y]) x = d[i][x];

	if (x == y) return x;
	for (int i = 18; i >= 0; i--)
		if (d[i][x] != d[i][y]) x = d[i][x], y = d[i][y];

	return d[0][x];
}

void upd(int idx,int p){
	int x = arr[idx],y = arr[idx + 1];
	int c = lca(x,y);

	if (!p) vec[c].erase(vec[c].find(idx));
	else {
		vec[c].insert(idx);
	}
}
signed main (){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m,q;
	cin>>n>>m>>q;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		v[a].pb(b);
		v[b].pb(a);
	}

	for (int i = 1; i <= m; i++)
		cin >> arr[i];

	dfs(1,1);
	for (int j = 1; j <= 18; j++)
		for (int i = 1; i <= n; i++)
			d[j][i] = d[j - 1][d[j - 1][i]];

	for (int i = 1; i < m; i++){
		int c = lca(arr[i],arr[i + 1]);
		vec[c].insert(i);
	}

	for (int i = 1; i <= m; i++){
		st[arr[i]].insert(i);
	}

	while (q--){
		int tp;
		cin>>tp;
		if (tp == 1){
			int pos,val;
			cin>>pos>>val;

			st[arr[pos]].erase(st[arr[pos]].find(pos));
			st[val].insert(pos);

			if (pos >= 1) upd(pos-1,0);
			if (pos + 1 <= m) upd(pos,0);
			arr[pos] = val;
			if (pos >= 1) upd(pos-1,1);
			if (pos + 1 <= m) upd(pos,1);
		}else{
			int l,r,x;
			cin>>l>>r>>x;

			multiset <int> :: iterator it = vec[x].lower_bound(l);
			if (it != vec[x].end() && *it < r){
				cout<<*it<<" "<<(*it) + 1<<endl;
			}else{
				if (st[x].size()){
					it = st[x].lower_bound(l);
					if (it != st[x].end() && *it <= r){
						cout<<(*it)<<" "<<(*it)<<endl;
					}
				}else{
					cout<<-1<<" "<<-1<<endl;
				}
				
			}
		}
	}
}

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