백준(BOJ) 1572 중앙값 ***

# 자료구조 #STL # 정렬

상당히 까다로운 문제였다.

우선 vector로 해서 푸는 방법과 비교해본다면

vector는 정렬할때 NlogN이 걸려 풀기가 어렵다.

이에 비해 set을 이용하게 되면 삭제, 삽입시(logN)이 걸려 해결 할 수 있다.

또한  삽입, 삭제를 할때 동일한 값이 중복해서 들어올 때와 현재 중앙값이 사라질 때 실수 했다.

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <utility>
#include <functional>
#define MAX 1000000
#define INF 987654321
#define MOD 1000000
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

int n,m,r=0,l=0,st=1,arr[250005];
multiset<int> ms;
multiset<int>::iterator iter=ms.begin(),tmp;
ll ans=0;

void my_update()
{
    if(l>r)iter--,l--,r++;
    if(l+1<r)iter++,l++,r--;
}
void my_insert(int in)
{
    ms.insert(in);
    if(ms.size()==1)
        iter=ms.begin();
    else
        *iter>in?l++:r++;
    my_update();
}
void my_delete(int in)
{
    /*tmp=ms.lower_bound(in);
    if(tmp==iter) iter++,r-=ms.size()>1;
    else in>*iter ? r--:l--;
    ms.erase(tmp);
    my_update();*/
    
    *iter<=in?r--:l--;
    if(*iter==in)iter++;
    ms.erase(ms.lower_bound(in));
    my_update();
}
void add_mid()
{ans+=*iter;}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&arr[i]);

    for(int i=1;i<=n;i++)
    {
        my_insert(arr[i]);
        if(m<i)my_delete(arr[i-m]);
        if(m<=i)add_mid();
    }
    printf("%lld",ans);
}