백준 문제풀이
백준 8462 - 배열의 힘 [Python]
Vermeil
2021. 7. 25. 00:18
https://www.acmicpc.net/problem/8462
8462번: 배열의 힘
자연수 \(n\)개로 이루어진 배열 \(a_1,a_2,a_3,\dots ,a_n\)이 있다. \(l\)부터 \(r\)까지 부분 배열은 \(a_l,a_{l+1},\dots , a_r\) 이다. \(K_s\)는 부분 배열 안에 있는 자연수 \(s\)의 개수이다. 부분 배열의 힘이란
www.acmicpc.net
[사용한 알고리즘]
Mo's
Sqrt Decomposition
엄청 신기하고 강력한 기술인 모쓰, 제곱근 분할법 기초문제이다.
모른다면 보고 오자. 진짜 별거 없지만, 오프라인 쿼리 문제에서 잘 써먹을 수 있다.
https://justicehui.github.io/hard-algorithm/2019/06/17/MoAlgorithm/
정렬 조건을 잘못짜서 계속 시간초과떴다.
[소스코드]
|
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
|
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 ########
|
cs |