BOJ 10355 Most Influential Pumpkin

문제

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

10355번: Most Influential Pumpkin

처음에 입력 수열 A가 주어지고, 각 쿼리마다 [l, r]에 1씩 더하고, 전체 수열의 중앙값을 구하라.

($N, Q<=60000$, 5초)

 

풀이

N제한과 시간제한의 범위를 보면, sqrt decomposition 을 의심해 볼 수 있다.

sqrt decomposition 의 기본적인 느낌은 NAIVE 한 풀이이다.

 

가장 먼저 $O(Nsqrt(N)log^2N)$ 풀이부터 살펴보자.

일단 전체 구간을 B개의 버팃으로 쪼갠 후, 각 버킷에는 수들을 정렬해서 관리한다.

 

업데이트는 완전히 포함하는 버킷은 버킷에 +1을 해주고, 아닌 곳에는 먼저 버킷의 값을 풀어서 내부의 값들에 더해준 후, 범위에 속하는 구간에만 +1해준다. 이후, 아닌곳은 다시 정렬해 준다.

 

쿼리는 파라마트릭 서치를 이용하여 값을 구해줄 건데, 각 버킷마다 그 수 이하인 수들의 수를 세서 더해주면 된다.

 

하지만 이 문제는 $O(Nsqrt(N)logN)$ 이하로 줄이기 위해서는 한가지 관찰이 필요하다.

한번에 수들에 +1씩만 더하니, 중앙값은 증가하지 않거나, 1증가한다.

파라마트릭 서치할 필요 없이, 전 답값을 계산해보고, 증가시킬지 말지만 정해주면 된다.

 

시간 복잡도 : $O(Nsqrt(N)logN)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 60000;

int N, K, B[MAXN+10], SQ, ans;
pii A[MAXN+10];

int main()
{
    int i, j;

    while(1)
    {
        scanf("%d%d", &N, &K);
        if(N==0 && K==0) break;
        SQ=200;

        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));

        vector<int> V;
        for(i=1; i<=N; i++)
        {
            scanf("%d", &A[i].first);
            A[i].second=i;
            V.push_back(A[i].first);
        }
        sort(V.begin(), V.end()); ans=V[N/2];

        for(i=0; i<=N/SQ; i++) sort(A+max(1, SQ*i), A+min(N+1, SQ*(i+1)));
        while(K--)
        {
            int l, r;
            scanf("%d%d", &l, &r);

            if(l/SQ==r/SQ)
            {
                for(i=max(1, l/SQ*SQ); i<min(N+1, (l/SQ+1)*SQ); i++) A[i].first+=B[l/SQ]; B[l/SQ]=0;
                for(i=max(1, l/SQ*SQ); i<min(N+1, (l/SQ+1)*SQ); i++) if(l<=A[i].second && A[i].second<=r) A[i].first++;
                sort(A+max(1, l/SQ*SQ), A+min(N+1, (l/SQ+1)*SQ));
            }
            else
            {
                for(i=max(1, l/SQ*SQ); i<min(N+1, (l/SQ+1)*SQ); i++) A[i].first+=B[l/SQ]; B[l/SQ]=0;
                for(i=max(1, l/SQ*SQ); i<min(N+1, (l/SQ+1)*SQ); i++) if(l<=A[i].second && A[i].second<=r) A[i].first++;
                sort(A+max(1, l/SQ*SQ), A+min(N+1, (l/SQ+1)*SQ));

                for(i=max(1, r/SQ*SQ); i<min(N+1, (r/SQ+1)*SQ); i++) A[i].first+=B[r/SQ]; B[r/SQ]=0;
                for(i=max(1, r/SQ*SQ); i<min(N+1, (r/SQ+1)*SQ); i++) if(l<=A[i].second && A[i].second<=r) A[i].first++;
                sort(A+max(1, r/SQ*SQ), A+min(N+1, (r/SQ+1)*SQ));

                for(i=l/SQ+1; i<r/SQ; i++) B[i]++;
            }

            int cnt=0;
            for(i=0; i<=N/SQ; i++)
            {
                cnt+=upper_bound(A+max(1, SQ*i), A+min(N+1, SQ*(i+1)), pii(ans-B[i], 0), [&](const pii &p, const pii &q) { return p.first<q.first; })-(A+max(1, SQ*i));
            }
            if(cnt<N/2+1) ans++;
            printf("%d\n", ans);
        }
    }
}​