백준 8462 - 배열의 힘 [Python]

https://www.acmicpc.net/problem/8462

8462번: 배열의 힘

[사용한 알고리즘]

Mo's

Sqrt Decomposition

 

 

 

엄청 신기하고 강력한 기술인 모쓰, 제곱근 분할법 기초문제이다.

 

모른다면 보고 오자. 진짜 별거 없지만, 오프라인 쿼리 문제에서 잘 써먹을 수 있다.

https://justicehui.github.io/hard-algorithm/2019/06/17/MoAlgorithm/

 

정렬 조건을 잘못짜서 계속 시간초과떴다.

 

[소스코드]

import sys, math
input = sys.stdin.readline
 
#input
def ip(): return int(input())
def fp(): return float(input())
def sp(): return str(input().rstrip())
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split())
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
############### Main! ###############
 
c = [0 for _ in range(1000001)]
def add(x):
    global res
    c[x] += 1
    res += (c[x] * 2 - 1) * x
 
def erase(x):
    global res
    c[x] -= 1
    res -= (c[x] * 2 + 1) * x
 
n, qr = mip()
a = [0] + lmip()
q = []
for i in range(qr):
    x, y = mip()
    q.append((i, x, y))
 
sqrtN = int(math.sqrt(n))
q.sort(key=lambda x:(x[1]//sqrtN, x[2]))
 
ans = [0 for _ in range(qr)]
 
res = 0
s = 0
e = 0
 
for i in range(qr):
    while s < q[i][1]: erase(a[s]); s += 1
    while s > q[i][1]: s -= 1; add(a[s])
    while e > q[i][2]: erase(a[e]); e -= 1
    while e < q[i][2]: e += 1; add(a[e])
    ans[q[i][0]] = res
 
print(*ans, sep='\n')
 
######## Priest W_NotFoundGD ########