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

AOJ 2170 Marked Ancestor

問題:
N頂点の根付き木,Q個のクエリ
クエリM v:頂点vを塗る
クエリQ v:頂点v以上で塗られている最も近いindexを答える
はじめは頂点1(root)だけが塗られている
N,Q<=10^5

文句:
問題文が意味不明(説明が足りなすぎる)
クエリQの原文は
Q v: (Query) Print the index of the nearest marked ancestor of node v which is nearest to it.
なのだが、これで自分自身を含むと誰が思えるんだろう

解法:
euler tour 1D版 + doubling + BIT でやった。
dbl[i][j]=頂点iから1くくj個上の頂点(不等号*2だとコメントアウトされる)
とeuler tourの配列を持っておき、マークするクエリにはeuler tourの入っていく方に+1,出てくほうに-1足す。答えるクエリは「1~vまで(の経路)で何個塗られてるか」がわかれば、doublingでにぶたんすればわかる。「」の中はBITでもてばよい。(euler tourの良い性質(関係ないところは+1と-1が打ち消し合う)を使っている)
のだが、もっと簡単な解法があった

先にMarkクエリを全部処理したと考えて、逆から見ていくと、そこで併合すればいいのでUnionFindでいける。ただし何回も同じ場所にmarkされる場合があることに注意(これも制約からは読み取れない,これは意地が悪い程度のレベルだと思う)

ミス:
long longにするのを忘れた

my code:

#include <iostream>
#include <vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
vector<int> G[100000],euler;
int dbl[100000][18],ff[100000],ss[100000],bit[200001],n,q;
int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-= i&-i;
	}
	return s;
}
void add(int i,int x){
	while(i<=2*n){
		bit[i]+=x;
		i+= i&-i;
	}
}
void dfs(int v){
	ff[v]=euler.size();
	euler.push_back(v);
	rep(i,G[v].size()) dfs(G[v][i]);
	ss[v]=euler.size();
	euler.push_back(v);
}
int main(){
	while(true){
		cin >> n >> q;
		if(n==0) break;
		euler.clear();
		rep(i,n) G[i].clear();
		rep(i,n) rep(j,18) dbl[i][j]=-1;
		rep(i,2*n+1) bit[i]=0;
		rep(i,n-1){
			int p;
			cin >> p;
			G[p-1].push_back(i+1);
			dbl[i+1][0]=p-1;
		}
		rep(i,17){
			rep(j,n){
				if(dbl[j][i]==-1) dbl[j][i+1]=-1;
				else dbl[j][i+1]=dbl[dbl[j][i]][i];
			}
		}
		dfs(0);
		add(ff[0]+1,1);
		add(ss[0]+1,-1);
		long long ans=0;
		rep(i,q){
			char c;
			int v;
			cin >> c >> v;
			v--;
			if(c=='M'){
				add(ff[v]+1,1);
				add(ss[v]+1,-1);
			}else{
				int x=sum(ff[v]+1);
				for(int j=17;j>=0;j--){
					if(dbl[v][j]!=-1 && sum(ff[dbl[v][j]]+1)>=x) v=dbl[v][j];
				}
				ans+=(v+1);
			}
		}
		cout << ans << endl;
	}
}