제출 #336243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336243		super_j6	Birthday gift (IZhO18_treearray)	C++14	56 / 100	3591 ms	262148 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 pii pair<int, pi>
#define f first
#define s second

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

void dfs(int c){
	for(int i = 1; i < k; i++) p[i][c] = ~p[i][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];
}

struct segTree{
	int l, r;
	segTree *tl, *tr;
	set<pii> s;
	
	segTree(int l, int r) : l(l), r(r){
		for(int i = l; i <= r; i++){
			s.insert({a[i], {i, i}});
			if(i < r) s.insert({lca(a[i], a[i + 1]), {i, i + 1}});
		}
		if(l != r){
			int mid = (l + r) / 2;
			tl = new segTree(l, mid);
			tr = new segTree(mid + 1, r);
		}
	}
	
	void add(int x){
		if(x < l || r < x) return;
		s.insert({a[x], {x, x}});
		if(x > l) s.insert({lca(a[x - 1], a[x]), {x - 1, x}});
		if(x < r) s.insert({lca(a[x], a[x + 1]), {x, x + 1}});
		if(l == r) return;
		tl->add(x), tr->add(x);
	}
	
	void del(int x){
		if(x < l || r < x) return;
		s.erase({a[x], {x, x}});
		if(x > l) s.erase({lca(a[x - 1], a[x]), {x - 1, x}});
		if(x < r) s.erase({lca(a[x], a[x + 1]), {x, x + 1}});
		if(l == r) return;
		tl->del(x), tr->del(x);
	}
	
	pi qry(int x, int y, int v){
		if(y < l || r < x) return {-2, -2};
		if(x <= l && r <= y){
			auto it = s.lower_bound({v, {0, 0}});
			return it != s.end() && it->f == v ? it->s : pi{-2, -2};
		}
		int mid = (l + r) / 2;
		if(x <= mid && mid + 1 <= y && lca(a[mid], a[mid + 1]) == v){
			return {mid, mid + 1};
		} 
		pi p = tl->qry(x, y, v);
		if(p.f != -2) return p;
		return tr->qry(x, y, v);
	}
};

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], a[i]--;
	
	segTree tre(0, m - 1);
	while(q--){
		int t;
		cin >> t;
		if(t & 1){
			int x, y;
			cin >> x >> y;
			x--, y--;
			tre.del(x);
			a[x] = y;
			tre.add(x);
		}else{
			int l, r, x;
			cin >> l >> r >> x;
			pi p = tre.qry(--l, --r, --x);
			cout << p.f + 1 << " " << p.s + 1 << endl;
		}
	}

	return 0;
}

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