読者です 読者をやめる 読者になる 読者になる

AOJ 2170 Marked Ancestor ver.2

別解を友人に教えてもらった
1.逆からunionfind
2.Euler tour + BIT + doubling
については
http://sigma425.hatenablog.com/entry/2014/08/05/232421の通り.

3.(new)
Euler tour + segtree
それぞれのノードは"marked ancestorの候補"を持っている.
更新クエリ:in[v]~out[v]を覆うようなブロック達について,(まだ書き込まれていないor今書こうとしている値が既に書き込まれた値の子孫である)なら書き込む.
解答クエリ:in[v]のノードから上に0まで見ていって,最も子孫側を答える.
anc(x,y):xがyのancestor は in[x]<in[y]&&out[y]>out[x] とかける
コード見たほうがわかりやすそう.
正当性:
まず,in[v]の上にvの先祖以外が書き込まれてないことが,vを含む区間がin[x]~out[x]と表せるならxがvの先祖であることからわかる.
また,書き込まれた値は必ずin[v]の上のどこかにあり,そのうち直近のものは必ず残っている(rewriteされてない)ことがわかる.

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
vector<int> G[100000],euler;
const int p2=262144;
int in[100000],out[100000],n,q;
int seg[p2*2-1];
void dfs(int v){
	in[v]=euler.size();
	euler.push_back(v);
	rep(i,G[v].size()) dfs(G[v][i]);
	out[v]=euler.size();
	euler.push_back(v);
}
bool anc(int x,int y){
	return in[x]<in[y]&&out[x]>out[y];
}
void change(int a,int b,int c,int l,int r,int k){
	if(b<=l||r<=a) return;
	if(a<=l&&r<=b){
		if(seg[k]==-1||anc(seg[k],c) ) seg[k]=c;
		return;
	}
	change(a,b,c,l,(l+r)/2,k*2+1);
	change(a,b,c,(l+r)/2,r,k*2+2);
}
int main(){
	while(true){
		cin >> n >> q;
		if(n==0) break;
		euler.clear();
		rep(i,n) G[i].clear();
		rep(i,p2*2-1) seg[i]=-1;
		rep(i,n-1){
			int p;
			cin >> p;
			G[p-1].push_back(i+1);
		}
		dfs(0);
		long long ans=0;
		change(in[0],out[0]+1,0,0,p2,0);
		rep(i,q){
			char c;
			int v;
			cin >> c >> v;
			v--;
			if(c=='M'){
				change(in[v],out[v]+1,v,0,p2,0);
			}else{
				int x=p2-1+in[v],ret=0;
				while(true){
					if(seg[x]!=-1 && anc(ret,seg[x])) ret=seg[x];
					if(x==0) break;
					x=(x-1)/2;
				}
				ans+=(ret+1);
			}
		}
		cout << ans << endl;
	}
}