2022.07.25. (Sparse Table, Lowest Common Ancestor) 풀이

다룬 태그들

• Sparse Table (ABC)
• Lowest Common Ancestor (DEFG)

A. [17435] 합성함수와 쿼리 (Gold I)

\( f^N(x) \)는 \( f^1(x), f^2(x), f^4(x), \ldots, f^{2^k}(x) \)의 적절한 합성으로 만들 수 있습니다.

그러니, Exponentiation by Squaring 하듯이 전처리를 돌리고

쿼리를 처리해주면 됩니다.

const int B = 20;
int spr[22][200020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> spr[0][i]; }
	for (int b = 1; b <= B; b++){
		for (int i = 1; i <= n; i++){
			spr[b][i] = spr[b-1][ spr[b-1][i] ];
		}
	}
	int q; cin >> q; while (q--){
		int k, x; cin >> k >> x;
		for (int b = B; b >= 0; b--){
			if (k>>b & 1){ x = spr[b][x]; }
		}
		cout << x << endl;
	}
}

B. [18783] Swapity Swapity Swap (Gold II)

\( M \)개의 수열 뒤집기 쿼리를 다 처리한 결과 순열을 \( p \)라고 합시다.

그럼, \( x \rightarrow f(x) \)로 함수를 하나 만들어볼 수 있습니다. (\( x \)번 위치에서 \( f(x) \)번 위치로 이동)

이렇게 한 뒤, \( f^N(x) \)를 구해주면 이는 모든 이동이 끝났을 때 \( x \)번 위치에 있던 소가 어디로 이동했는지에 대한 함수가 되고, 이를 토대로 답을 출력해주면 됩니다.

const int N = 29;
int per[100020], spr[30][100020];
int res[100020];

void Main(){
	int n, m, k; cin >> n >> m >> k;
	for (int i = 1; i <= n; i++){ per[i] = i; }
	while (m--){
		int l, r; cin >> l >> r;
		while (l < r){ swap(per[l], per[r]); l += 1; r -= 1; }
	}
	for (int i = 1; i <= n; i++){ spr[0][ per[i] ] = i; }
	for (int j = 1; j <= N; j++){
		for (int i = 1; i <= n; i++){
			spr[j][i] = spr[j-1][ spr[j-1][i] ];
		}
	}
	for (int i = 1; i <= n; i++){
		int ptr = i;
		for (int j = N; j >= 0; j--){
			if (k>>j & 1){ ptr = spr[j][ptr]; }
		}
		res[ptr] = i;
	}
	for (int i = 1; i <= n; i++){ cout << res[i] << endl; }
}

C. [3117] YouTube (Gold I)

'합성함수와 쿼리' 문제랑 다른 점이 없습니다.

그냥 \( f(x) \)를 추천 영상으로 둘러댔을 뿐입니다.

int arr[100020];
int spr[40][100020];

void Main(){
	ll n, k, m;
	cin >> n >> k >> m; m -= 1;
	for (int i = 1; i <= n; i++){
		cin >> arr[i];
	}
	for (int i = 1; i <= k; i++){
		cin >> spr[0][i];
		//cout << "SPR " << 0 << ' ' << i << " = " << spr[0][i] << endl;
	}
	for (int i = 1; i <= 30; i++){
		for (int j = 1; j <= k; j++){
			spr[i][j] = spr[i-1][ spr[i-1][j] ];
			//cout << "SPR " << i << ' ' << j << " = " << spr[i][j] << endl;
		}
	}
	for (int i = 1; i <= n; i++){
		int p = arr[i];
		for (ll j = 30; j >= 0; j--){
			if (m & 1<<j){
				//cout << "IF " << m << ' ' << j << ' ' << (m & 1<<j) << endl;
				p = spr[j][p];
			}
		}
		cout << p << ' ';
	}
}

D. [11438] LCA 2 (Platinum V)

LCA를 빠르게 구하는 문제입니다.

Sparse Table을 사용해서 해결해주면 됩니다.

vector<int> adj[100020]; int dep[100020];
const int B = 20; int spr[22][100020];
void dfs(int now, int pre){
	spr[0][now] = pre; dep[now] = dep[pre]+1;
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dfs(nxt, now);
	}
}

int lca(int v, int w){
	if (dep[v] > dep[w]){ swap(v, w); }
	int dif = dep[w] - dep[v];
	for (int b = B; b >= 0; b--){
		if (dif>>b & 1){ w = spr[b][w]; }
	}
	if (v == w){ return v; }
	for (int b = B; b >= 0; b--){
		if (spr[b][v] != spr[b][w]){ v = spr[b][v]; w = spr[b][w]; }
	}
	return spr[0][v];
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i < n; i++){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	dfs(1, 1);
	for (int b = 1; b <= B; b++){
		for (int v = 1; v <= n; v++){ spr[b][v] = spr[b-1][ spr[b-1][v] ]; }
	}
	int q; cin >> q; while (q--){
		int v, w; cin >> v >> w;
		cout << lca(v, w) << endl;
	}
}

E. [14942] 개미 (Platinum V)

LCA를 구하듯이 (부모 정점, 그 정점까지의 거리)를 저장하는 Sparse Table을 만든 뒤,

정점까지의 거리가 한계를 넘지 않는 동안 계속 위로 올려주면 됩니다.

const int B = 16;
pl2 spr[20][100020];
int arr[100020];

vector<pi2> adj[100020];
void dfs(int now, int pre){
	for (pi2 p : adj[now]){ int nxt = p.fr;
		if (nxt == pre){ continue; }
		int dst = p.sc; spr[0][nxt] = {now, dst};
		dfs(nxt, now);
	}
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i < n; i++){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	dfs(1, -1);
	for (int j = 1; j <= B; j++){
		for (int v = 1; v <= n; v++){
			int w = spr[j-1][v].fr;
			spr[j][v].fr = spr[j-1][w].fr;
			spr[j][v].sc = spr[j-1][v].sc + spr[j-1][w].sc;
		}
	}
	for (int i = 1; i <= n; i++){
		int ptr = i;
		for (int j = B; j >= 0; j--){
			if (spr[j][ptr].fr == 0){ continue; }
			if (spr[j][ptr].sc > arr[i]){ continue; }
			arr[i] -= spr[j][ptr].sc; ptr = spr[j][ptr].fr;
		}
		cout << ptr << endl;
	}
}

F. [20295] 사탕 배달 (Platinum III)

사탕의 종류가 5개밖에 없습니다.

그래서, Sparse Table에 (부모 정점, 가면서 만난 사탕 종류의 Bitmasking)을 저장해둘 수 있습니다.

두 정점 사이의 경로는 \( v \Rightarrow \text{lca}(v, w) \Rightarrow w \)이기 때문에,

LCA를 찾기 위해 올라가는 과정에서 Bitmask의 값도 같이 업데이트해주면 됩니다.

(또는 그냥 따로 올려줘도 상수의 차이가 있을 뿐 시간복잡도는 동일합니다.)

const int N = 20;
int arr[100020];
vector<int> adj[100020];
pi2 spr[100020][22];
bool chk[6];

int dep[100020];
void dfs(int now, int pre){
	dep[now] = dep[pre]+1;
	spr[now][0] = {pre, (1<<arr[now]) | (1<<arr[pre])};
	for (int nxt : adj[now]){
		if (nxt == pre){ continue; }
		dfs(nxt, now);
	}
}

pi2 lca(int a, int b){
	if (dep[a] > dep[b]){ swap(a, b); }
	int da = dep[a], db = dep[b]; int dif = db - da;
	int bit = (1<<arr[a]) | (1<<arr[b]);
	for (int j = N; j >= 0; j--){
		if (dif & 1<<j){ bit |= spr[b][j].sc; b = spr[b][j].fr; }
	}
	if (a == b){ return {a, bit}; }
	for (int j = N; j >= 0; j--){
		if (spr[a][j].fr != spr[b][j].fr){
			bit |= spr[a][j].sc; a = spr[a][j].fr;
			bit |= spr[b][j].sc; b = spr[b][j].fr;
		}
	}
	bit |= spr[a][0].sc | spr[b][0].sc;
	return { spr[a][0].fr, bit };
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; chk[ arr[i] ] = 1; }
	for (int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	dfs(1, 1);
	for (int j = 1; j <= N; j++){
		for (int i = 1; i <= n; i++){
			spr[i][j].fr = spr[ spr[i][j-1].fr ][j-1].fr;
			spr[i][j].sc = spr[i][j-1].sc | spr[ spr[i][j-1].fr ][j-1].sc;
		}
	}
	int q; cin >> q;
	int ptr = -1;
	while (q--){
		int a, b; cin >> a >> b;
		if (ptr == -1){
			if (!chk[b]){ cout << "CRY" << endl; }
			else{ cout << "PLAY" << endl; }
			ptr = a; continue;
		}
		if (ptr == a){
			if (arr[a] != b){ cout << "CRY" << endl; }
			else{ cout << "PLAY" << endl; }
			continue;
		}
		pi2 p = lca(ptr, a);
		if (p.sc & 1<<b){ cout << "PLAY" << endl; }
		else{ cout << "CRY" << endl; }
		ptr = a;
	}
}

G. [13511] 트리와 쿼리 2 (Platinum III)

이번에는 Sparse Table에 (부모 정점, 간선의 가중치 합)를 들고 있어봅시다.

그럼 1번 쿼리는 \( v \Rightarrow \text{lca}(v, w) \)의 간선 가중치 합 + \( w \Rightarrow \text{lca}(v, w) \)의 간선 가중치 합으로 처리할 수 있습니다.

 

2번 쿼리는 어떻게 처리할까요?

\( v \)부터 시작해서 정점에 0, 1, 2, ..., k의 번호를 매겨볼 수 있습니다.

이제, LCA의 번호를 기준으로 답이 \( v \)쪽에 있는지, \( w \)쪽에 있는지 판별해 준 뒤

그 쪽 방향에서 정확히 몇 칸을 올려야 하는지 계산 후 출력하면 됩니다.

vector<pi2> adj[100020];

int dep[100020];
const int B = 20; pl2 spr[22][100020];
void dfs(int now, int pre){
	for (pi2 p : adj[now]){
		int nxt = p.fr; ll dst = p.sc;
		if (nxt == pre){ continue; }
		spr[0][nxt] = {now, dst}; dep[nxt] = dep[now] + 1;
		dfs(nxt, now);
	}
}

pl2 lca(int v, int w){ ll dst = 0;
	if (dep[v] > dep[w]){ swap(v, w); }
	int dif = dep[w] - dep[v];
	for (int b = B; b >= 0; b--){
		if (dif>>b & 1){ dst += spr[b][w].sc; w = spr[b][w].fr; }
	}
	if (v == w){ return {v, dst}; }
	for (int b = B; b >= 0; b--){
		if (spr[b][v].fr != spr[b][w].fr){
			dst += spr[b][v].sc; v = spr[b][v].fr;
			dst += spr[b][w].sc; w = spr[b][w].fr;
		}
	}
	dst += spr[0][v].sc; v = spr[0][v].fr;
	dst += spr[0][w].sc; w = spr[0][w].fr;
	return {v, dst};
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i < n; i++){
		int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	dfs(1, 0);
	for (int b = 1; b <= B; b++){
		for (int v = 1; v <= n; v++){
			int w = spr[b-1][v].fr;
			spr[b][v].fr = spr[b-1][w].fr;
			spr[b][v].sc = spr[b-1][v].sc + spr[b-1][w].sc;
		}
	}
	int q; cin >> q; while (q--){
		int typ; cin >> typ;
		if (typ == 1){
			int v, w; cin >> v >> w;
			cout << lca(v, w).sc << endl;
		}
		if (typ == 2){
			int v, w, k; cin >> v >> w >> k; k--;
			int l = lca(v, w).fr;
			int dv = dep[v] - dep[l], dw = dep[w] - dep[l];
			if (dv == k){ cout << l << endl; continue; }
			if (dv < k){ swap(v, w); swap(dv, dw); k = dv+dw - k; }
			for (int b = B; b >= 0; b--){
				if (k>>b & 1){ v = spr[b][v].fr; }
			}
			cout << v << endl;
		}
	}
}