BOJ 15899 - 트리의 색깔 (ett, 머지소트트리)

https://www.acmicpc.net/problem/15899

기록용

 

<문제설명>

최대 2e5개의 정점을 갖는 트리가 주어진다. 각 정점마다 최대 2e5의 값(색)을 하나씩 갖는다.

 

다음 쿼리를 처리하자

v c : 정점v를 루트로 하는 서브트리에서 값이 c이하인 정점의 수

 

<풀이>

서브트리를 구간트리로 처리할 수 있는지? 할 수 있다면 머지소트트리가 가장 적합함 (update쿼리가 없어서 가능)

 

ett번호를 붙여주고 머지소트트리 일반적인 풀이 쓰면 된다.

 

 

<코드>

const int MAX = 2e5 + 4;
const int MOD = 1e9 + 7;
const int SMAX = (1 << 19);

int n, qq, C, l[MAX], r[MAX];
vector<int> seg[SMAX], g[MAX];

int counter = 0;
void makelr(int u, int p) {
	l[u] = counter++;
	for (int v : g[u]) if (v != p) makelr(v, u);
	r[u] = counter-1;
}

void construct() {
	for (int i = SMAX / 2 - 1; i >= 1; i--) {
		seg[i] = seg[i * 2 + 1];
		seg[i].insert(seg[i].end(), seg[i * 2].begin(), seg[i * 2].end());
		sort(seg[i].begin(), seg[i].end());
	}
}

int val(int s, int e, int k, int i = 1, int ns = 0, int ne = SMAX / 2 - 1) {
	if (e < ns || ne < s) return 0;
	if (s <= ns && ne <= e) 
		return upper_bound(seg[i].begin(), seg[i].end(), k) - seg[i].begin();
	int md = (ns + ne) / 2;
	return val(s, e, k, i * 2, ns, md) + val(s, e, k, i * 2 + 1, md + 1, ne);
}

int main() {
	FAST; cin >> n >> qq >> C;
	vector<int> inp(n+1);
	for (int i = 1; i <= n; i++) cin >> inp[i];
	for (int i = 0, u, v; i < n - 1; i++) {
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	makelr(1, 0);
	for (int i = 1; i <= n; i++) 
		seg[l[i] + SMAX / 2].push_back(inp[i]);
	
	construct();

	ll ans = 0;
	for (int i = 0, v, c; i < qq; i++) {
		cin >> v >> c;
		ans += val(l[v], r[v], c);
		ans %= MOD;
	}
	cout << ans << '\n';
}