티스토리 뷰

문제 풀이

[BOJ 13548] 수열과 쿼리 6

RiKang 2017. 11. 11. 18:29

선행 : 모스 알고리즘


모스 알고리즘으로 해결 가능하다.


[Li, Ri] 쿼리 구간에 대해


COUNT[x] = (A[j]==x) 인 j 의 갯수


COUNT2[x] = (COUNT[j]==x) 인 j 의 갯수


위와 같은 정보를 저장한다면, COUNT2[x] !=0 을 만족하는 최대의 x가 정답이 됨은 문제 설명 상 자명하다.


또한, [Li, Ri] 일 때의 정답과 [L(i+1), R(i+1)] 일 때의 정답의 차이는 |L(i+1)-L(i)| + |R(i+1)-R(i)|  이하이다.

(* 추가or삭제되는 A[j] 의 개수보다 정답이 더 크게 변할 순 없기 때문이다. 정답이 증가할 때와 감소할 때 모두 생각해 보면 간단히 증명 가능)


이를 이용해 'COUNT2[x] !=0 을 만족하는 최대의 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
62
63
64
65
66
// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<queue>
#define PII pair<int,int>
#define PIII pair<PII,int>
 
using namespace::std;
 
const int N = 100005, M = 1000005, SQRT_N = 300;
PII query[N];
PIII order[N];
int cnt[M];
int cnt2[M];
int a[N];
int n,q,an;
int ans[M];
int removed[M];
 
void add(int idx){
    cnt2[cnt[a[idx]]]--;
    cnt[a[idx]]++;
    cnt2[cnt[a[idx]]]++;
    an = max(an, cnt[a[idx]]);
}
 
void erase(int idx){
    cnt2[cnt[a[idx]]]--;
    cnt[a[idx]]--;
    cnt2[cnt[a[idx]]]++;
}
 
void go_query(PII prev, PII now){
    int l1 = prev.first;
    int r1 = prev.second;
    int l2 = now.first;
    int r2 = now.second;
    for(int i = l1-1; i>=l2; i--) add(i); // l1 > l2 인 경우, 구간이 늘어났으므로 노드 추가
    for(int i = r1+1; i<=r2; i++) add(i); // r1 < l2 인 경우, 구간이 늘어났으므로 노드 추가
    for(int i = l1; i<l2; i++) erase(i); // l1 < l2 인 경우, 구간이 줄었으므로 노드 삭제
    for(int i = r1; i>r2; i--) erase(i); // r1 < l2 인 경우, 구간이 늘어났으므로 노드 삭제
}
 
int main(){
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
    }
    cnt2[0= n+1;
    an = 0;
    scanf("%d",&q);
    for(int i=1; i<=q; i++){
        scanf("%d %d",&query[i].first, &query[i].second);
        order[i].first = PII(query[i].first/SQRT_N, query[i].second);
        order[i].second = i;
    }
    sort(order+1, order+q+1);  // order[0]=(0,0) 점임을 이용하기 때문에 a는 1-indexed여야 함.
    for(int i=1; i<=q; i++){
        go_query(query[order[i-1].second], query[order[i].second]);
        while(cnt2[an]==0) an--;
        ans[order[i].second] = an;
    }
    for(int i=1; i<=q; i++)
        printf("%d\n",ans[i]);
    return 0;
}
cs


'문제 풀이' 카테고리의 다른 글

0/1 냅색 ( 0/1 knapsack problem )  (0) 2017.11.15
[BOJ 8462] 배열의 힘  (0) 2017.11.11
[BOJ 13548] 수열과 쿼리 6  (0) 2017.11.11
[BOJ 13518] 트리와 쿼리 9  (0) 2017.11.03
[CF 371 D] Animals and Puzzle  (0) 2017.10.31
[BOJ 4008] 특공대  (0) 2017.10.31