백준 1572, 백준 9426, Segment Tree, std::multiset
많은걸 배울 수 있었던 문제.
두 가지 해결 방법을 배웠는데, 첫 번째는 segtree 로, 두 번째는 multiset 으로 푸는 법을 배웠다.
-
segtree 를 이용한 방법.
첫 번째 segtree 를 이용하는 방법은 각 숫자의 범위가 0 부터 65536 까지 제한된 것을 이용한다.
$0$ 부터 $65536$ 까지의 구간을 나눠서 각 구간에 포함되는 숫자들이 나타나는 개수를 저장하고, $(K+1)/2$ 번째로 큰 숫자를 찾는 방식이다.
각 $node$의 값을 각 $node$ 가 나타내는 범위 내에 있는 숫자들의 개수를 저장하고,
$query$ 는 각 자식 $node$ 들의 값을 탐색하며 $V$ 번째로 큰 숫자를 찾아낸다.
어떤 $node$ 가 나타내는 범위가 $[l:r]$ 일때, $leftnode$ 는 $[l:mid]$, $rightnode$ 는 $[mid+1:r]$ 구간까지 나타낸다.
만약 $leftnode$ 구간 숫자들의 개수가 현재 $node$ 구간의 개수와 같다면, $leftnode$ 로 이동한다.
만약 $leftnode$ 구간의 개수가 더 적다면, $V$ 번째로 큰 숫자는 $leftnode$ 의 구간에 없으므로 $rightnode$ 로 이동한다.
이를 반복하여 $leaf$ 까지 이동하면 $V$ 번째로 큰 숫자를 찾을 수 있다.
-
std::multiset 을 이용한 방법.
내가 처음에 생각했던 방법과 가까운 방법이다.
$multiset$ 이라는 자료 구조에 대해 잘 몰랐다. C++ STL 공부가 더 필요하다.
중앙값보다 작은 숫자들과 중앙값보다 큰 숫자들 두 가지로 $K$개 숫자들을 구분할 수 있다.
제거되는 숫자 $r$, 새로 들어오는 숫자 $x$ 가 중앙값 $m$ 보다 큰지, 작은지 경우의 수를 나누어 해결 하려고 했지만 shiftps 의 풀이를 보니 그럴 필요가 없었다.
중앙값 $m$ 보다 작은 숫자들을 저장하는 $lo$, 크거나 같은 숫자들을 저장하는 $hi$ 두 개의 $multiset$ 이 필요하다.
제거되는 숫자 $r$ 을 $lo$ 나 $hi$ 에서 찾아서 제거 한 다음,
$lo$ 의 크기가 $hi$ 보다 커질때 까지 $hi$ 에서 가장 작은 숫자들을 $lo$ 에 옮겨 담고,
다시 $lo$의 크기가 $hi$ 보다 작아질때 까지 $lo$ 에서 가장 큰 숫자들을 $hi$ 에 옮겨 담으면
$hi$ 에서 가장 작은 숫자가 중앙값이 된다.
Source Code
두 문제는 같은 문제다.
//segtree 를 사용한 방법.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define Msize 65536
#define ll long long
struct segtree {
int tree[Msize * 4];
segtree() {
memset(tree, 0, sizeof(tree));
}
int query(int val, int node, int nodeLeft, int nodeRight) {
if (nodeLeft == nodeRight) return nodeLeft;
int mid = (nodeLeft + nodeRight) / 2;
if (val <= tree[node * 2]) return query(val, node * 2, nodeLeft, mid);
else return query(val - tree[node * 2], node * 2 + 1, mid + 1, nodeRight);
}
int update(int idx, int val, int node, int nodeLeft, int nodeRight) {
if (idx < nodeLeft || idx > nodeRight) return tree[node];
if (nodeLeft == nodeRight) {
tree[node] += val;
return tree[node];
}
int mid = (nodeLeft + nodeRight) / 2;
tree[node] = update(idx, val, node * 2, nodeLeft, mid) + update(idx, val, node * 2 + 1, mid + 1, nodeRight);
return tree[node];
}
};
segtree SEG;
int N, K;
int input[250250];
ll ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for (int i = 0; i < N; ++i) {
cin >> input[i];
}
for (int i = 0; i < K; ++i) {
SEG.update(input[i], 1, 1, 0, Msize);
}
ans = SEG.query((K + 1) / 2, 1, 0, Msize);
for (int i = K; i < N; ++i) {
SEG.update(input[i], 1, 1, 0, Msize);
SEG.update(input[i - K], -1, 1, 0, Msize);
int medium = SEG.query((K + 1) / 2, 1, 0, Msize);
ans += medium;
}
printf("%lld\n", ans);
return 0;
}
// multiset 을 사용한 문제다.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
#define Msize 65536
#define ll long long
int N, K;
int input[250250];
vector<int> seed;
multiset<int> lo, hi;
ll ans;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K;
for (int i = 0; i < K; ++i) {
cin >> input[i];
lo.emplace(input[i]);
}
while (lo.size() >= hi.size()) {
hi.emplace(*lo.rbegin());
lo.erase(lo.find(*lo.rbegin()));
}
ans = *hi.begin();
for (int i = K; i < N; ++i) {
cin >> input[i];
auto r = lo.find(input[i - K]);
if (r != lo.end()) {
lo.erase(r);
}
else hi.erase(hi.find(input[i - K]));
lo.emplace(input[i]);
while (lo.size() < hi.size()) {
lo.emplace(*hi.begin());
hi.erase(hi.begin());
}
while (lo.size() >= hi.size()) {
hi.emplace(*lo.rbegin());
lo.erase(lo.find(*lo.rbegin()));
}
ans += *hi.begin();
}
printf("%lld\n", ans);
return 0;
}