백준 12986 - 화려한 마을 2

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

$O((N+Q)\sqrt N \log N)$ 솔루션 - Mo's + Indexed heap

Mo's 알고리즘 적용을 위해 쿼리를 정렬한다.

 

그리고 -100000부터 100000까지의 값을 index로 취급하면 가장 많이 출연한 원소의 횟수를 indexed heap로 찾을 수 있다.

 

그러면 각 쿼리를 처리하면서 원소의 출연 횟수를 구역을 횡단할 때마다 $O(\log N)$의 시간 복잡도로 갱신하게 되고 쿼리의 답은 max indexed heap의 top이 된다.

 

시간 복잡도 : $O((N+Q)\sqrt N \log N)$

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
template <typename T>
struct Elem {
  int i;
  T w;
  bool operator < (const Elem &o) const {
    return w != o.w ? w > o.w : i < o.i;
  }
  bool operator == (const Elem &o) const {
    return w == o.w and i == o.i;
  }
  bool operator > (const Elem &o) const {
    return w != o.w ? w < o.w : i < o.i;
  }
  bool operator <= (const Elem &o) const {
    return *this < o or *this == o;
  }
  bool operator >= (const Elem &o) const {
    return *this > o or *this == o;
  }
};
 
template <typename T>
struct idx_heap {
  Elem<T> *arr;
  int *pos;
  int size;
 
  idx_heap(int _n) : size(0) {
    arr = new Elem<T>[_n + 1];
    pos = new int[_n + 1];
  }
 
  ~idx_heap() {
    delete[] arr;
    delete[] pos;
  }
 
  void push(int i, T w) {
    arr[++size] = {i, w};
    pos[i] = size;
    up(size);
  }
 
  void change(int i, T w) {
    int cur = pos[i];
    auto k = arr[cur];
    arr[cur].w = w;
    k < w ? down(cur) : up(cur);
  }
 
  void update(int i, T w) {
    int cur = pos[i];
    auto k = arr[cur];
    arr[cur].w += w;
    k < arr[cur] ? down(cur) : up(cur);
  }
 
  void up(int cur) {
    while (cur > 1) {
      if (arr[cur] >= arr[cur / 2]) break;
      swap(arr[cur], arr[cur / 2]);
      pos[arr[cur].i] = cur;
      cur /= 2;
    }
    pos[arr[cur].i] = cur;
  }
 
  void down(int cur) {
    while (cur * 2 <= size) {
      int mx;
      if (cur * 2 == size or arr[cur * 2] < arr[cur * 2 + 1]) mx = cur * 2;
      else mx = cur * 2 + 1;
      if (arr[cur] <= arr[mx]) break;
      swap(arr[cur], arr[mx]);
      pos[arr[cur].i] = cur;
      cur = mx;
    }
    pos[arr[cur].i] = cur;
  }
 
  T pop() {
    T ret = arr[1].i;
    arr[1] = arr[size--];
    pos[arr[1].i] = 1;
    down(1);
    return ret;
  }
 
  void del(int i) {
    int cur = pos[i];
    auto k = arr[cur];
    arr[cur] = arr[size--];
    pos[arr[cur].i] = cur;
    k < arr[cur] ? down(cur) : up(cur);
  }
};
 
int rt;
int n, q;
int ar[100001];
 
struct query
{
  int l, r, order;
  bool operator < (const query &arg) const
  {
    int x = r / rt, y = arg.r / rt;
    return x == y ? l < arg.l : x < y;
  }
} qry[100001];
 
void operation(int idx, bool add, idx_heap<int> &pq)
{
  int val = ar[idx];
  int amount = (add ? 1 : -1);
  pq.update(val, amount);
}
 
int ans[100001];
 
void solve()
{
  cin >> n >> q;
  rt = sqrt(n);
  idx_heap<int> pq(200005);
  for (int i = 0; i <= 200005; i++) pq.push(i, 0);
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
    ar[i] += 1e5;
  }
 
  for (int i = 0; i < q; i++)
  {
    int go, to;
    cin >> qry[i].l >> qry[i].r;
    qry[i].order = i;
  }
  sort(qry, qry + q);
 
  int lo = 1, hi = 0;
  for (int i = 0; i < q; i++)
  {
    auto here = qry[i];
    while (lo < here.l)
    {
      operation(lo++, false, pq);
    }
 
    while (hi < here.r)
    {
      operation(++hi, true, pq);
    }
 
    while (hi > here.r)
    {
      operation(hi--, false, pq);
    }
 
    while (lo > here.l)
    {
      operation(--lo, true, pq);
    }
 
    ans[here.order] = pq.arr[1].w;
  }
 
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

$O((N+Q)\sqrt N)$ 솔루션 - Mo's

위에서 좀 더 똑똑하게 생각해보자. 과연 최댓값을 찾기 위해 우선순위 큐를 써야 할까?

 

우선순위 큐 대신 값의 등장 횟수의 횟수를 테이블로 관리하자. 그러면 다음에 따라 최댓값을 $O(1)$에 찾을 수 있다.

 

mp(i) := 원소 i가 출현한 횟수

mp2(i) := i번 출현한 원소의 개수

mx := 출현 횟수의 최댓값

원소가 추가되는 경우

원소 x가 5개 있고 원소 x를 하나 더 추가한다고 해보자. 그리고 mp2(5) = 1이라고 해보자.

 

그러면 mp(x)의 값은 하나 증가한다. 이에 따라 mp2(5)의 값은 하나 줄고 mp2(6)의 값은 하나 증가한다. mx는 이 중에서 더 큰 6을 취한다.

원소가 제거되는 경우

위 상황과 똑같다고 했을 때 mp2(5)에서 1이 줄어들어 0이 된다. 그러면 5가 최댓값이 아니라 4가 최대값이 됨은 자명하므로 mx에서 1을 빼줘야 한다.

 

만약 mp2(5)가 아직 살아있다면 어떤 원소가 아직 5번 출현했다는 뜻이므로 빼면 안 된다.

 

그리고 mp를 갱신하면 된다.

 

이런 방식으로 $O(1)$답 갱신을 할 수 있고 mo's를 수행하면 된다. 잘 이해가 되지 않으면 전체 코드를 참조하자.

 

시간 복잡도 : $O((N + Q) \sqrt N)$

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int rt;
int n, q;
int ar[100001];
int mp[200001];
int mp2[100001];
int mx;
 
struct query
{
  int l, r, order;
  bool operator < (const query &arg) const
  {
    int x = r / rt, y = arg.r / rt;
    return x != y ? x < y : l < arg.l;
  }
} qry[100001];
 
void operation(int idx, bool add)
{
  int val = ar[idx];
  if (add)
  {
    --mp2[mp[val]];
    ++mp[val];
    ++mp2[mp[val]];
    mx = max(mx, mp[val]);
  }
  else
  {
    if (mp2[mp[val]]) --mp2[mp[val]];
    if (!mp2[mp[val]] and mx == mp[val]) --mx;
    --mp[val];
    ++mp2[mp[val]];
  }
}
 
int ans[100000];
 
void solve()
{
  cin >> n >> q;
  rt = (int)round(sqrt(n));
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
    ar[i] += 1e5;
  }
 
  for (int i = 0; i < q; i++)
  {
    int go, to;
    cin >> qry[i].l >> qry[i].r;
    qry[i].order = i;
  }
  sort(qry, qry + q);
 
  int lo = 1, hi = 0;
  for (int i = 0; i < q; i++)
  {
    auto here = qry[i];
    while (lo < here.l)
    {
      operation(lo++, false);
    }
 
    while (hi < here.r)
    {
      operation(++hi, true);
    }
 
    while (hi > here.r)
    {
      operation(hi--, false);
    }
 
    while (lo > here.l)
    {
      operation(--lo, true);
    }
 
    ans[here.order] = mx;
  }
 
  for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

당연히 빠른게 두 번째 풀이다.