제출 #1140110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1140110		Agageldi	Birthday gift (IZhO18_treearray)	C++17	56 / 100	4094 ms	92140 KiB

treearray

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

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 5;

ll n, t, a[N], q, m, vis[N], sp[N][30], lvl[N];
vector <int> v[N];
multiset <int> s[N];
int kth_anscestor(int x,int y) {
	for(int i = 0; i <= 20; i++) {
		if(y&(1 << i)) x = sp[x][i];
	}
	return x;
}
int find(int x,int y) {
	if(lvl[x] < lvl[y]) {
		y = kth_anscestor(y,lvl[y] - lvl[x]);
	}
	if(lvl[y] < lvl[x]) {
		x = kth_anscestor(x,lvl[x] - lvl[y]);
	}
	if(x == y) return x;
	for(int i = 20;i >= 0; i--) {
		if(sp[x][i] != sp[y][i]) {
			x = sp[x][i];
			y = sp[y][i];
		}
	}
	return sp[x][0];
}
void dfs(int x,int cnt) {
	lvl[x] = cnt;
	vis[x] = 1;
	for(auto i:v[x]) {
		if(vis[i]) continue;
		sp[i][0] = x;
		dfs(i,cnt + 1);
	}
}

int main () {
	// ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	for(int i = 1; i <= m; i++) {
		cin >> a[i];
		s[a[i]].insert(i);
	}
	dfs(1,1);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= 20; j++) {
			if(sp[i][j - 1])sp[i][j] = sp[sp[i][j - 1]][j - 1];
		}
	}
	for(int i = 1; i < m; i++) {
		s[find(a[i], a[i + 1])].insert(i);
	}
	for(int i = 1; i <= q; i++) {
		int pos, x, l, r;
		cin >> t;
		if(t == 1) {
			cin >> pos >> x;
			if(a[pos] == x) continue;
			if(pos > 1 && pos < n){
				s[a[pos]].erase(*s[a[pos]].find(pos));
			}
			s[x].insert(pos);
			if(pos > 1) {
				int tt = find(a[pos],a[pos - 1]);
				if(s[tt].find(pos-1)!=s[tt].end())s[tt].erase(s[tt].find(pos - 1));
				tt = find(x,a[pos - 1]);
				s[tt].insert(pos - 1);
			}
			if(pos < n) {
				int tt = find(a[pos],a[pos + 1]);
				if(s[tt].find(pos)!=s[tt].end())s[tt].erase(s[tt].find(pos));
				tt = find(x,a[pos + 1]);
				s[tt].insert(pos);
			}
			a[pos] = x;
			continue;
		}
		cin >> l >> r >> x;
		if(!sz(s[x])) {
			cout <<"-1 -1\n";
			continue;
		}
		auto p = lower_bound(s[x].begin(),s[x].end(),l);
		if(p == s[x].end() || (*p) > r) {
			cout << "-1 -1\n";
			continue;
		}
		if(a[(*p)] == x) {
			cout << (*p) <<" " << (*p) << '\n';
			continue;
		}
		if((*p) + 1 > r) {
			cout <<"-1 -1\n";
			continue;
		}
		cout << (*p) << " " << (*p) + 1 << '\n';
	}
}

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