제출 #382800

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382800		maximath_1	Birthday gift (IZhO18_treearray)	C++11	100 / 100	1176 ms	78800 KiB

treearray

// First idea (O(QNlogN))
// build a segment tree, segment L to R has value LCA(a[L..R])
// for every query, fix left of subarray and binary search for R
// to get a vertex with depth equal to the required vertex, then compare
// this can be done as depth(LCA(a[L..R-1])) <= depth(LCA(a[L..R]))

// Main solution O(QlogN)
// In what condition does depth(LCA(a[L..R-1])) < depth(LCA(a[L..R])) occur?
// that is when a[R] is in a different subtree to a[L..R-1]
// notice that we can just consider one representative of a[L..R-1] and compare to a[R]
// lca(a[L..R]) = lca(a[R-1], a[R])
// maintain all consecutive pairs

#include <stdio.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 200005;
const int LG = (int)log2(MX) + 2;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
 
#define gc getchar//_unlocked //can't for window server
void cin(int &x){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	x = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		x = (x << 1) + (x << 3) + (c - '0');
	if(neg) x = -x;
}
 
int n, m, q, a[MX];
vector<int> adj[MX];
set<int> ans_1[MX], ans_2[MX];
int anc[MX][LG], depth[MX];
 
void dfs(int nw, int bf){
	anc[nw][0] = bf;
	depth[nw] = depth[bf] + 1;
	for(int nx : adj[nw]) if(nx != bf)
		dfs(nx, nw);
}
 
void build_lca(){
	for(int j = 1; j < LG; j ++)
		for(int i = 1; i <= n; i ++)
			anc[i][j] = anc[anc[i][j - 1]][j - 1];
}
 
int lca(int u, int v){
	if(depth[u] < depth[v]) swap(u, v);
	int diff = depth[u] - depth[v];
	for(int i = LG - 1; i >= 0; i --)
		if(diff & (1 << i)) u = anc[u][i];
	if(u == v) return u;
	for(int i = LG - 1; i >= 0; i --)
		if(anc[u][i] != anc[v][i])
			u = anc[u][i], v = anc[v][i];
	return anc[u][0];
}
 
int main(){
	cin(n); cin(m); cin(q);
 
	for(int u, v, i = 1; i < n; i ++){
		cin(u); cin(v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
 
	dfs(1, 1);
	build_lca();
 
	for(int i = 1; i <= m; i ++){
		cin(a[i]);
		ans_1[a[i]].insert(i);
	}
 
	for(int i = 1; i < m; i ++){
		int lc = lca(a[i], a[i + 1]);
		ans_2[lc].insert(i);
	}
 
	for(int tp, l, r, ps, v; q --;){
		cin(tp);
		if(tp == 1){
			cin(ps); cin(v);
			if(ps > 1){
				int get = lca(a[ps - 1], a[ps]);
				ans_2[get].erase(ans_2[get].find(ps - 1));
				get = lca(a[ps - 1], v);
				ans_2[get].insert(ps - 1);
			}
			if(ps < m){
				int get = lca(a[ps], a[ps + 1]);
				ans_2[get].erase(ans_2[get].find(ps));
				get = lca(v, a[ps + 1]);
				ans_2[get].insert(ps);
			}
			ans_1[a[ps]].erase(ans_1[a[ps]].find(ps));
			a[ps] = v;
			ans_1[a[ps]].insert(ps);
		}else{
			cin(l); cin(r); cin(v);
			auto it = ans_2[v].lower_bound(l);
			if(it != ans_2[v].end() && l <= *it && *it + 1 <= r)
				printf("%d %d\n", *it, *it + 1);
			else{
				it = ans_1[v].lower_bound(l);
				if(it != ans_1[v].end() && l <= *it && *it <= r)
					printf("%d %d\n", *it, *it);
				else
					printf("-1 -1\n");
			}
		}
	}
	
	return 0;
}

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