백준 13548 - 수열과 쿼리 6

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

 

모스 알고리즘의 연습 문제 중 하나이다.

 

$O((N + M) \sqrt M)$으로 처리를 하되, 다음을 이용해야 한다.

 

포인터가 한 index 움질일 때마다 구간에 속한 수의 출현 빈도의 변화량 d는 $-1 \leq d \leq 1$ 이므로 $O(1)$에 출현 횟수의 변화를 계산할 수 있다.

 

이를 구현하기 위해 어떤 수를 index로 하여 그 출현 횟수를 저장하는 배열 mp와 어떤 출현 횟수를 index로 하여 그 출현 횟수의 횟수를 저장하는 배열 counter를 둔다.

 

이렇게 되면 구간이 1씩 길어질 때마다 새로 포함된 값 x를 mp에 반영하기 전에 기존 구간에서 x의 출현 횟수를 저장한 counter를 바꿔줘야 한다.

 

counter의 값을 수정한 후 새롭게 포함된 원소를 mp에 반영하면 된다.

 

이 연산을 함수로 구현하면 다음과 같다.

 

void take(int idx)
{
  if (mp[ar[idx]])
    --counter[mp[ar[idx]]];
  ++counter[++mp[ar[idx]]];
  cur = max(cur, mp[ar[idx]]);
}

 

위 코드에서 cur는 구간 최빈값의 출현 횟수이다.

 

구간이 1씩 짧아질 때는 mp에 반영하기 전 구간에서 지워질 수의 빈도가 최빈값의 출현 횟수와 같은지 확인해야 한다.

 

counter를 변경한 후 counter에서 기존 출현 횟수가 0이면 최대 출현 횟수가 1 낮아졌다는 뜻이므로 cur에서 1을 빼주면 된다.

 

변경 후 counter의 값이 1 이상이라면 구간 내의 다른 최빈값이 그 횟수를 유지하고 있다는 뜻이므로 cur를 빼서는 안된다.

 

위 과정이 끝나고 mp를 갱신하면 된다.

 

다음은 위 과정을 함수로 구현한 것이다.

 

void kill(int idx)
{
  --counter[mp[ar[idx]]];
  if (mp[ar[idx]] == cur && !counter[mp[ar[idx]]])
    --cur;
  ++counter[--mp[ar[idx]]];
}

 

이제 남은건 오프라인 쿼리를 수행하면서 위 두 함수로 적절한 값을 저장하고 출력하면 된다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int rt;

struct mo_node
{
  int l, r, n;
  mo_node(int s, int e, int num): l(s), r(e), n(num) {}
  mo_node(): mo_node(0, 0, 0) {}

  bool operator < (const mo_node &arg) const
  {
    int a = r / rt, b = arg.r / rt;
    if (a == b) return l < arg.l;
    return a < b;
  }
};

int n;
int ar[100001];
int mp[100001];
int counter[100001];
mo_node query[100000];
int res[100000];
int cur;

void take(int idx)
{
  if (mp[ar[idx]])
    --counter[mp[ar[idx]]];
  ++counter[++mp[ar[idx]]];
  cur = max(cur, mp[ar[idx]]);
}

void kill(int idx)
{
  --counter[mp[ar[idx]]];
  if (mp[ar[idx]] == cur && !counter[mp[ar[idx]]])
    --cur;
  ++counter[--mp[ar[idx]]];
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> ar[i];
  rt = sqrt(n);

  int q;
  cin >> q;

  for (int i = 0; i < q; ++i)
  {
    int a, b;
    cin >> a >> b;
    query[i] = mo_node(a, b, i);
  }

  sort(query, query + q);
  int x = 1, y = 0;

  for (int i = 0; i < q; ++i)
  {
    while (y < query[i].r)
      take(++y);
    while (y > query[i].r)
      kill(y--);
    while (x < query[i].l)
      kill(x++);
    while (x > query[i].l)
      take(--x);
    
    res[query[i].n] = cur;
  }

  for (int i = 0; i < q; ++i)
    cout << res[i] << '\n';
}