https://codeforces.com/contest/1527/problem/C
시간 2초, 메모리 256MB

input :

• t (1 ≤ t ≤ 105)
• n (2 ≤ n ≤ 105)
• a1, a2, …, an (0 ≤ ai ≤ 100)

output :

• For each test case, print a single integer — the sum of the weight of all subsegments of a.
  각 테스트 케이스에서 모든 연속된 부분 배열의 weight의 합을 출력하시오.

조건 :

• The weight of a sequence is defined as the number of unordered pairs of indexes (i,j) (here i<j) with same value (ai = aj)
  weight는 정렬되지 않은 배열에서 각 원소가 동일한 경우 이를 묶을 수 있는데 이러한 묶음의 개수를 뜻합니다.

---

가장 기초적인 방식 brute force라면? 1만개가 들어왔을 때 아마 각 문자열에 어떤 수가 있는지 알아야 하니까 최소한 2번의 반복문이 필요해서 시간이 터질 것이다.

일단 풀이를 보고 이해를 하고 싶었는데 그것도 이해가 안 됐다. 아래의 댓글 중 CQTshadow 라는 분의 설명을 보았고 드뎌 갈피를 잡았었다.

이 문제를 dp를 이요해서 풀어보라고 한다. 부분 문자열의 경우도 길이를 통해 나눌 수 있을 것이고 가능은 할 것 같다.

그러면 어떤 기능이 존재해야 하냐?

dp의 인덱스

여기서 만드는 dp의 인덱스는 무엇을 뜻하냐? 당연히 입력받은 배열의 원소를 뜻한다. 그렇다면 dp의 계산은 어떻게 해야 할까? 원소들이 배열에 위치한 인덱스를 이용한다. 이 부분이 무슨 말인지 아리까리 했다.

1 2 1 1 을 입력 받았을 때

현재 idx는 3이다. (1 2 1)
이미 동일한 값 '1'이 존재하기 때문에 얘를 포함하는 경우를 기록하고 싶다. 이 때 부분 배열로 만드려면 [1, 3]이여야 한다.

현재 idx가 4일때. (1 2 1 1)
이미 동일한 값들이 존재하는데 이를 포함하는 배열을 만들고 싶다. idx 3에 위치하는 놈을 포함하고 싶다면 [3, 4], [2, 4], [1, 4]를 넣을 수 있고.(물론 인덱스 1에 동일한 원소가 존재하겠지만 이건 무시하고 개수를 세아리는 것이다. 현재의 목적은 3에 있는 놈만으로 unordered pair를 만들어 개수를 세는 것)

idx 1에 위치한 놈을 넣고 싶다면 [1, 4]를 넣을 수 있다. 그러면 둘을 동시에 넣으려면? dp[idx - 1]에 기록된 값을 포함하는 것이다.

현재 배열의 인덱스

그래서 만들 수 있는 배열의 경우 1 ~ 자기의 인덱스 까지인 것이다. 그래서 인덱스의 총합을 저장하는 것이다.

그렇다면 인덱스를 기록해 두는 것이 필요하다. 이를 위해 딕셔너리를 만들어 준다.

딕셔너리에 값이 존재한다면 ans에 값을 추가하도록 하고 그렇지 않다면 초기화를 한다.
반복문을 돌 때는 계속해서 딕셔너리에 값을 업데이트해야 한다.

import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))
    dp = [0] * (n + 1)
    temp = dict()

    for idx in range(1, n + 1):
        dp[idx] += dp[idx - 1]

        if data[idx - 1] in temp:
            dp[idx] += temp[data[idx - 1]]
        else:
            temp[data[idx - 1]] = 0
        temp[data[idx - 1]] += idx

    print(sum(dp))