yukicoder : No.1030 だんしんぐぱーりない

典型の詰め合わせなので教育向け。
https://yukicoder.me/problems/no/1030

問題

根付き木を成す有向グラフが与えられる。
各辺は根を向いている。
各点には、スコアが設定されている。

今このグラフにK個のビーバーがおり、それぞれの現在地が与えられる。
以下のクエリに順次答えよ。

• ビーバー1体を指定した頂点に動かす
• ビーバーの区間が与えられる。全ビーバーが辺をたどって到達可能な頂点における、最大スコアを答えよ

解法

まず、各頂点のスコアを、自身の頂点及びその祖先におけるスコアの最大値に更新しておく。
そうすると、後者のクエリが「到達可能な頂点すべて」から「全ビーバーの位置のLCA」に置き換えられる。
あとは複数点のLCAを求めることになるが、事前にオイラーツアーを行い全頂点の番号を振りなおしておくと、番号が最小値と最大値の2点に対応する頂点のLCAを求めればよくなる。
そこで、オイラーツアーとLCAを求める処理を書いたうえで、各ビーバーの所在地におけるオイラーツアー訪問順番号の最大値・最小値を求めるSegTreeを持っておけばよい。

int N;
int P[101010];
int L[101010][21],R[101010][21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<pair<int,int>> cand;
	FOR(i,N) {
		cin>>P[i+1];
		cand.push_back({P[i+1],i+1});
	}
	FOR(j,20) R[N+1][j]=N+1;
	vector<int> V;
	FOR(i,N+1) {
		while(V.size()&&P[V.back()]>P[i]) V.pop_back();
		if(V.size()) L[i][0]=V.back();
		V.push_back(i);
	}
	V.clear();
	V.push_back(N+1);
	for(i=N;i>=1;i--) {
		while(V.size()&&P[V.back()]>P[i]) V.pop_back();
		if(V.size()) R[i][0]=V.back();
		V.push_back(i);
	}
	FOR(i,20) FOR(j,N) L[j+1][i+1]=L[L[j+1][i]][i],R[j+1][i+1]=R[R[j+1][i]][i];
	
	set<int> D;
	D.insert(0);
	D.insert(N+1);
	sort(ALL(cand));
	reverse(ALL(cand));
	ll ret=0;
	FORR(c,cand) {
		x=c.second;
		auto it=D.insert(x).first;
		i=*prev(it);
		j=*next(it);
		int cur=x;
		for(y=19;y>=0;y--) if(R[cur][y]<j) cur=R[cur][y],ret+=1<<y;
		cur=x;
		for(y=19;y>=0;y--) if(L[cur][y]>i) cur=L[cur][y],ret+=1<<y;
	}
	cout<<ret<<endl;
	
}

まとめ

先日JOIの問題解いてて「ビ太郎ってなんだ…？」と思った。