[BOJ 8462] 배열의 힘

선행 : 모스 알고리즘

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

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

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

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

그러면 모스 알고리즘이 돌아가면서 COUNT[x] 값이 갱신될 때, 정답도 같이 갱신해주면 된다.

// 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;
}