티스토리 뷰
반응형
선행 : 모스 알고리즘
모스 알고리즘으로 해결 가능하다.
[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 13518] 트리와 쿼리 9 (0) | 2017.11.03 |
[CF 371 D] Animals and Puzzle (0) | 2017.10.31 |
[BOJ 4008] 특공대 (0) | 2017.10.31 |