수열과 쿼리 4 [BOJ 13546]

수열과 쿼리 0과 수열과 쿼리 7과 같은 문제인데, 이 문제가 가장 기본형인 것 같다. 수열과 쿼리 6의 응용 버전이기도 하다. 이 문제의 풀이를 모르겠다면 수열과 쿼리 6을 먼저 풀어보기 바란다. 아래는 수열과 쿼리 6 풀이 링크이다.

https://unorderedmap.tistory.com/31

수열과 쿼리 6 [BOJ 13548]

 

문제 요약

길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. (단, 수열의 각 원소는 10만 이하)

l r : max{ |x-y| : l<=x, y<=r이고 A[x]=A[y] } 출력

 

사용 알고리즘

Mo's Algorithm

 

풀이

수열의 원소가 같은 두 점 중 구간 내에서 가장 멀리 떨어져있는 두 점 사이의 거리를 구하라는 문제이다. 수열과 쿼리 6을 풀 때 구간 내 가장 많이 등장하는 수의 빈도수를 찾기 위해 빈도수를 저장하는 배열을 하나 만들고, 그 빈도수의 빈도수를 저장하는 배열을 하나 만들었다. 또한 이를 통해 최댓값을 시간 안에 구할 수 있었다. 이번에도 이와 같은 방식으로 문제를 풀 것이다.

그에 앞서 이 문제를 풀 때 list라는 STL을 사용한다. 이 문제를 풀 때는 front(), back(), pop_front(), push_front(), pop_back(), push_back()이 모두 필요하고, list는 이를 지원한다. 그냥 원소를 앞에서도 넣고 뺄 수 있는 stack이라고 생각하면 된다. 아무튼 list[i]에는 현재 보는 구간 안에서 A[x]=i인 모든 x가 담겨있다. 구간의 왼쪽을 업데이트할 때는 front와 관련된 연산으로, 오른쪽을 업데이트할 때는 back과 관련된 연산으로 처리해주면, list의 원소들이 항상 정렬된 상태로 유지된다. 이제 새로운 배열 c[]를 관리하는데, c[j]는 현재 j=max{ |x-y| : l<=x, y<=r이고 A[x]=A[y]=i }인 i들의 수로 정의한다. 이렇게 정의하면 수열과 쿼리 6에서 구한 것처럼 c[j]!=0인 j의 최댓값을 시간 안에 구할 수 있다.

c[]를 업데이트를 할 때에는 list를 업데이트하기 전 상황에서 c의 위치를 찾아 1을 빼주고, 업데이트한 후 상황에서 c의 위치를 찾아 1을 더해주면 된다. 각 업데이트는 모두 O(1)이기 때문에 전체 시간복잡도는 O(NsqrtN)이다.

 

코드

#include <bits/stdc++.h>
#define SIZE 100002
typedef long long ll;
using namespace std;
struct Query
{
    int id, s, e;
};
int A[SIZE], c[SIZE], sqrtN, K, ans[SIZE], res;
Query q[SIZE];
list<int> idx[SIZE];
bool comp(Query x, Query y)
{
    if (x.s/sqrtN==y.s/sqrtN) {
        if (x.e==y.e) return x.s<y.s;
        return x.e<y.e;
    }
    return x.s/sqrtN<y.s/sqrtN;
}
void mo_radd(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].push_back(x);
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
void mo_rdis(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].pop_back();
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
void mo_ladd(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].push_front(x);
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
void mo_ldis(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].pop_front();
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
int main()
{
    int N, M, i;
    scanf ("%d %d", &N, &K);
    sqrtN=sqrt(N);
    for (i=1; i<=N; i++) scanf ("%d", &A[i]);
    scanf ("%d", &M);
    for (i=0; i<M; i++) {
        scanf ("%d %d", &q[i].s, &q[i].e);
        q[i].id=i;
    }
    sort(q, q+M, comp);
    int s=q[0].s, e=q[0].e;
    for (i=s; i<=e; i++) mo_radd(i);
    ans[q[0].id]=res, c[0]=K;
    for (i=1; i<M; i++) {
        while (s>q[i].s) mo_ladd(--s);
        while (e<q[i].e) mo_radd(++e);
        while (s<q[i].s) mo_ldis(s++);
        while (e>q[i].e) mo_rdis(e--);
        while (c[res]==0) res--;
        ans[q[i].id]=res;
    }
    for (i=0; i<M; i++) printf("%d\n", ans[i]);
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장