백준1572 중앙값

작성일 | In

문제 링크

  • http://icpc.me/1572

사용 알고리즘

  • set

시간복잡도

  • O(n log n)

풀이

예전에 세그먼트 트리를 이용해서 merge sort tree를 만든 뒤, 이 문제처럼 풀어보려고 했으나 TLE를 받고 포기했던 문제입니다.

pbds(policy based data structure)에 있는 트리가 set에 find_by_order와 같은 메소드를 추가해놓은 것과 비슷한 역할을 한다길래 연습삼아 사용해봤습니다.
해당 자료구조를 사용하면 Too Easy

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<ll, ll> p;
typedef tree<p, null_type, less<p>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

ordered_set s;
ll ans;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, k; cin >> n >> k;
	vector<ll> v(n+1);
	for(int i=1; i<=n; i++) cin >> v[i];
	for(int i=1; i<=k; i++) s.insert({v[i], i});

	ans += (*s.find_by_order((k+1)/2-1)).first;
	for(int i=k+1; i<=n; i++){
		s.erase({v[i-k], i-k});
		s.insert({v[i], i});
		ans += (*s.find_by_order((k+1)/2-1)).first;
	}
	cout << ans;
}