배열의 힘

• 온라인 쿼리로는 구간에서 저 값을 빠르게 계산하는 방법이 잘 떠오르지 않는다.
• 오프라인 쿼리로 처리해서 Mo's algorithm을 사용하려고 생각하자.
• 어떤 구간에 대해서, 각 숫자의 등장 횟수 Ks와 구하는 값을 저장해두자. 구간을 한 칸 더 늘릴때는, 늘어난 구간의 값이 x라면, 기존 정답에서 Kx*Kx*x 를 빼고 Kx를 1 증가시킨 다음에 다시 Kx*Kx*x 를 더하면 된다. 순서를 좀 바꾸면 정답에 (Kx+1)*(Kx+1)*x - Kx*Kx*x = (2*Kx+1)*x를 더한 뒤 Kx를 1 증가시키는 것. 이것은 O(1)에 해결된다
• 구간을 한칸 줄이는 것도 똑같은 과정으로 O(1)에 해결된다
• 따라서 이 두가지 연산으로 Mo's algorithm을 돌리면, 총 시간복잡도는 쿼리 정렬에 드는 O(qlogq)과 쿼리 처리에 걸리는 O( (n+q)*sqrt(n))*O(1) 을 합친 O(qlogq + (n+q)*sqrt(n))이 된다.

"""Solution code for "BOJ 8462. 배열의 힘".

- Problem link: https://www.acmicpc.net/problem/8462
- Solution link: http://www.teferi.net/ps/problems/boj/8462
"""

import sys
from teflib import mosalgo


def main():
    # pylint: disable=unused-variable
    n, t = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]
    queries = []
    for i in range(t):
        l, r = [int(x) for x in sys.stdin.readline().split()]
        queries.append((l - 1, r, i))

    count = [0] * (max(a) + 1)

    def add(beg, end, ans):
        for a_i in a[beg:end]:
            ans += (count[a_i] * 2 + 1) * a_i
            count[a_i] += 1
        return ans

    def delete(beg, end, ans):
        for a_i in a[beg:end]:
            count[a_i] -= 1
            ans -= (count[a_i] * 2 + 1) * a_i
        return ans

    answers = mosalgo.mo(queries, add, delete)
    print(*answers, sep='\n')


if __name__ == '__main__':
    main()

• Dependency: teflib.mosalgo.mo