티스토리 뷰

문제 풀이

[BOJ 8462] 배열의 힘

RiKang 2017. 11. 11. 18:44
반응형

선행 : 모스 알고리즘


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


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


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

위와 같은 정보를 저장하자.

그러면 모스 알고리즘이 돌아가면서 COUNT[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
// 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];
long long a[N];
int n,q;
long long an;
long long ans[M];
int removed[M];
 
void add(int idx){
    long long ks = cnt[a[idx]], s = a[idx];
    an-= ks*ks*s;
    cnt[a[idx]]++;
    ks++;
    an+= ks*ks*s;
}
 
void erase(int idx){
    long long ks = cnt[a[idx]], s = a[idx];
    an-= ks*ks*s;
    cnt[a[idx]]--;
    ks--;
    an+= ks*ks*s;
}
 
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 %d",&n,&q);
    for(int i=1; i<=n; i++){
        scanf("%lld",&a[i]);
    }
    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]);
        ans[order[i].second] = an;
    }
    for(int i=1; i<=q; i++)
        printf("%lld\n",ans[i]);
    return 0;
}
cs


반응형

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

최장 증가 부분 수열 ( LIS )  (0) 2017.11.15
0/1 냅색 ( 0/1 knapsack problem )  (0) 2017.11.15
[BOJ 13548] 수열과 쿼리 6  (0) 2017.11.11
[BOJ 13518] 트리와 쿼리 9  (0) 2017.11.03
[CF 371 D] Animals and Puzzle  (0) 2017.10.31