Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 2170 - Marked Ancestor (ふたたび)

問題 : Marked Ancestor

問題概要 :
大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :

・頂点$v$ の色を赤色に変える.
・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.

$1 \leqq N,\ Q \leqq 10^5$


解法 :

昨日のAnimals で使ったテクが内包されていたので流用.
range-max segment tree と行き掛け順で列にすることでオンラインクエリも大丈夫になります.

コード :

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<int> G[100000];
int par[100000];
int ord[100000], dst[100000], rev[200000], time;

void dfs(int v, int p)
{
	par[v] = p;
	ord[v] = time++;
	rev[time - 1] = v;
	
	for (int i = 0; i < G[v].size(); i++){
		if (G[v][i] != p){
			dfs(G[v][i], v);
		}
	}
	dst[v] = time++;
}

int seg[1 << 19], lazy[1 << 19];

void eval(int k)
{
	seg[k] = max(seg[k], lazy[k]);
	if (k < (1 << 18) - 1){
		lazy[k * 2 + 1] = max(lazy[k * 2 + 1], lazy[k]);
		lazy[k * 2 + 2] = max(lazy[k * 2 + 2], lazy[k]);
	}
	lazy[k] = 0;
}

void updateNode(int k)
{
	seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
}

void changeMax(int a, int b, int x, int k = 0, int l = 0, int r = 1 << 18)
{
	eval(k);
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		lazy[k] = max(lazy[k], x);
		eval(k);
		return;
	}
	
	changeMax(a, b, x, k * 2 + 1, l, l + r >> 1);
	changeMax(a, b, x, k * 2 + 2, l + r >> 1, r);
	updateNode(k);
}

int get(int a, int k = 0, int l = 0, int r = 1 << 18)
{	
	eval(k);
	if (a + 1 <= l || r <= a) return (-1);
	
	if (a <= l && r <= a + 1){
		return (seg[k]);
	}
	
	int lch = get(a, k * 2 + 1, l, l + r >> 1);
	int rch = get(a, k * 2 + 2, l + r >> 1, r);
	updateNode(k);
	return (max(lch, rch));
}

int main()
{
	int N, Q;
	
	while (scanf("%d %d", &N, &Q) && N){
		for (int i = 0; i < N; i++) G[i].clear();
		
		for (int i = 1; i < N; i++){
			int v;
			scanf("%d", &v);
			G[--v].push_back(i);
		}
		
		time = 0;
		dfs(0, -1);
		memset(seg, 0, sizeof(seg));
		memset(lazy, 0, sizeof(lazy));
		
		long long int ans = 0;
		for (int i = 0; i < Q; i++){
			char t[10];
			int v;
			scanf("%s %d", t, &v);
			--v;
			
			if (t[0] == 'Q'){
				ans += rev[get(ord[v])] + 1;
			}
			else {
				changeMax(ord[v], dst[v] + 1, ord[v]);
			}
		}
		
		printf("%lld\n", ans);
	}
	
	return (0);
}