BOJ 33523 체리 컴퍼니

문제 링크입니다.

문제 요약

정점이 $N$개이고 부모의 정점 번호가 자식의 정점 번호보다 작은 rooted tree가 주어집니다. 이 트리의 $L,L+1,\cdots,R-1,R$번 정점을 포함하는 부분 그래프가 몇 개의 서브트리로 구성된 포레스트인지 $Q$번 구하세요.

풀이

연속한 번호의 정점들만을 쿼리로 받고, 트리에서 부모의 정점 번호가 자식보다 작다는 조건으로부터 관찰을 시도합시다. 결국 우리에게 필요한 것은 부모 정점이 없는 정점의 개수입니다. 매번 부모 정점이 있는지 없는지를 확인하는 작업은 귀찮습니다. 만약 우리가 확실히 부모 정점이 주어진 구간 안에 들어오지 않으리라는 걸 알 수 있다면 작업이 쉬울 텐데요…

만약 쿼리가 $L$이 작은 것부터 순서대로 들어온다면 어떨까요? 부모 정점 쪽이 작은 번호기 때문에, $L$이 늘어날 때마다 기존에 부모 정점이던 정점이 사라지고 그 직계 자식 정점들이 새로운 부모 정점 후보가 될 겁니다. 그 정점들이 구간 안에 들어온다면 서브트리 개수가 늘어나는 거죠.

이 문제에서는 쿼리를 수행하면서 실제로 트리에 어떤 조작을 가하는 게 아니기 때문에, 쿼리를 처리하는 순서를 마음대로 정할 수 있습니다! 그러니 아까 하고 싶었던, $L$이 작은 것부터 순서대로 처리하면서 부모 정점 후보를 관리하는 풀이를 쓸 수 있습니다. 세그먼트 트리를 이용해 구간 내의 부모 정점 후보의 개수를 구해 주면 전체 문제를 ${\cal O}((N+Q) \lg N)$의 시간 복잡도에 해결할 수 있습니다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

struct Query{
	int idx, l, r;
};

vector<Query> Q; vector<int> e[303030];
int ans[303030], fen[303030];

void upd(int i, int v){
	for(;i<=300000;i+=i&-i)fen[i]+=v;
}

int qry(int i){
	int ret = 0; for(;i;i-=i&-i) ret+=fen[i]; return ret;
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 2; i <= n; i++){
		int a; cin >> a; e[a].push_back(i);
	}
	int q; cin >> q; for(int i = 1; i <= q; i++){
		int l, r; cin >> l >> r; Q.push_back({i, l, r});
	}
	sort(Q.begin(), Q.end(), [&](const Query& a, const Query& b){
		return a.l < b.l;
	});
	int L = 1;
	upd(1, 1);
	for(auto [idx, l, r] : Q){
		while(L != l){
			for(auto t : e[L]) upd(t, 1);
			upd(L++, -1);
		}
		ans[idx] = qry(r);
	}
	for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}