티스토리 뷰

알고리즘 관련/BOJ

BOJ)13548 수열과 쿼리 6

JASON 자손9319 2017. 9. 3. 21:41

문제: icpc.me/13548


길이가 N인 수열이 주어질 때 구간 i j 사이에 가장 많이 등장한 수가 몇번 등장했는지 출력하는 문제이다.


이 문제를 온라인으로 수행하려고하면 굉장히 힘들어 보인다. 하지만 업데이트가 이루어지지 않기 때문에 오프라인 쿼리 문제로 변형시켜서 풀어볼 수 있다.


따라서 이 문제를 mo's algorithm을 이용하여 풀건데 가장 많이 등장하는 수를 결정해야 하기 때문에 현재까지 가장 많이 등장하는 수를 계속 가지고 있어야하고


각각의 수가 몇번 등장하였나 배열을 a, i번 등장한 수가 몇개 있나 배열을 b에 각각 저장해두면 


현재 쿼리의 답이 x면 만약 add로 인하여 추가 된 b가 x보다 크다면 x를 증가시켜주고 


erase로 인하여 x만큼 등장한 수가 없어진다면 x를 감소시켜주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, sz, a[100010], ans[100010], curr, cnt[100010], b[100010];
struct qry {
    int lo, hi, idx;
    qry(int lo, int hi, int idx) :lo(lo), hi(hi), idx(idx) {};
    qry() {}
    bool operator<(const qry& x) {
        int lidx = hi / sz;
        int ridx = x.hi / sz;
        return lidx == ridx ? lo < x.lo : lidx < ridx;
    }
}q[100010];
void add(int num) {
    if (cnt[num])
        b[cnt[num]]--;
    cnt[num]++;
    b[cnt[num]]++;
    curr = max(curr, cnt[num]);
}
void erase(int num) {
    b[cnt[num]]--;
    if (cnt[num] == curr&&!b[cnt[num]])
        curr--;
    cnt[num]--;
    b[cnt[num]]++;
}
int main() {
    scanf("%d"&n);
    sz = sqrt(n);
    for (int i = 0; i < n; i++)scanf("%d"&a[i]);
    scanf("%d"&m);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d%d"&x, &y);
        q[i] = qry(x - 1, y - 1, i);
    }
    sort(q, q + m);
    int lo = 0, hi = 0;
    add(a[0]);
    for (int i = 0; i < m; i++) {
        auto &next = q[i];
        int nlo = next.lo, nhi = next.hi;
        for (int i = lo; i < nlo; i++)
            erase(a[i]);
        for (int i = lo - 1; i >= nlo; i--)
            add(a[i]);
        for (int i = hi + 1; i <= nhi; i++)
            add(a[i]);
        for (int i = hi; i > nhi; i--)
            erase(a[i]);
        lo = nlo;
        hi = nhi;
        ans[next.idx] = curr;
    }
    for (int i = 0; i < m; i++)
        printf("%d\n", ans[i]);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)11003 최소값 찾기  (1) 2017.09.05
BOJ)1460 진욱이의 농장  (0) 2017.09.05
BOJ)13548 수열과 쿼리 6  (0) 2017.09.03
BOJ)2419 사수아탕  (0) 2017.08.27
BOJ)2370 시장 선거 포스터  (1) 2017.08.21
BOJ)3073 집으로 가는 길  (0) 2017.08.21
댓글
댓글쓰기 폼