BOJ 2336 - 굉장한 학생 (세그트리, 수학, 기하)

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

바로 이전에 풀었던 유형과 유사

 

<문제설명>

n명의 학생이 동점자 없는 시험을 세번 치른다.

 

i번 학생의 1,2,3차 시험 등수 < j번 학생의 1,2,3차 시험 등수일 경우 i번 학생은 j번학생보다 대단하다.

 

본인보다 대단한 학생이 없는 경우 그 학생은 굉장한 학생이라고 할 때, 굉장한 학생의 수를 구하라

 

<풀이>

(입력에서 1번 인덱스에 오는 숫자 i는 i번 학생이 1등했다는 의미)

 

각 학생마다 1,2,3차 등수를 tuple ran[MAX]에 저장한다.

ex) ran[3] = {x,y,z}  : 3번학생이 1차시험 x등 2차시험 y등 3차시험 z등했음.

1차시험의 등수를 기준으로 ran을 정렬한 후에, y와 z만 가지고 비교해 주면 된다.

 

아래 그림을 구현하면 된다.

모든 학생의 등수가 distinct하므로 세그먼트 트리로 구할 수 있다.

 

y값을 인덱스로, z값을 값으로 갖는 mnq를 만들어서 아래와 같은 코드로 답을 도출할 수 있다.

 

int ans = n;
for (int i = 1,x,y,z; i <= n; i++) {
	tie(x, y, z) = ran[i];
	if (val(0, y) < z) ans--;
	update(y, z);
}

 

<코드>

int n, seg[SMAX];
T ran[MAX];

void update(int i, int x) {
	i += SMAX / 2;
	seg[i] = x;
	while (i > 1) {
		i /= 2;
		seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
	}
}

int val(int s, int e, int node, int ns, int ne) {
	if (e < ns || ne < s) return INF;
	if (s <= ns && ne <= e) return seg[node];
	int mid = (ns + ne) / 2;
	return min(val(s, e, node * 2, ns, mid), val(s, e, node * 2 + 1, mid + 1, ne));
}
int val(int s, int e) { return val(s, e, 1, 0, SMAX / 2 - 1); }

int main() {
	FAST; cin >> n;
	for (int j = 0,x; j < n; j++) {
		cin >> x;
		get<0>(ran[x]) = j;
	}
	for (int j = 0, x; j < n; j++) {
		cin >> x;
		get<1>(ran[x]) = j;
	}
	for (int j = 0, x; j < n; j++) {
		cin >> x;
		get<2>(ran[x]) = j;
	}
	sort(ran, ran + n+1);

	memset(seg, 0x3f, sizeof(seg));

	int ans = n;
	for (int i = 1,x,y,z; i <= n; i++) {
		tie(x, y, z) = ran[i];
		if (val(0, y) < z) ans--;
		update(y, z);
	}
	
	cout << ans << '\n';
}