C. Sequence Pair Weight #721 Div.2


https://codeforces.com/contest/1527/problem/C
2秒、256 MBメモリ
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 iweightは、整列されていない配列の各要素が同じであれば、それらをグループ化することができ、これはこれらのグループの数を表す.
  • 最も基礎的な方法で暴力を振るうなら?1万個ある場合、文字列ごとにどのような方法があるかを知る必要がある可能性があるので、少なくとも2回繰り返し、時間が爆発します.
    まず解答を見てから理解しようと思ったが、まだ理解できなかった.下記のコメントでは、CQTshadowの説明を見て、頭を整理するのは難しいです.
    この問題をdpで解いてください.一部の文字列については、長さで区切ることもできますが、可能です.
    では、どんな機能があるのでしょうか.

    dpのインデックス


    ここで作成したdpのインデックスはどういう意味ですか?もちろん入力された配列の要素を指します.ではdpの計算はどうすればいいのでしょうか.要素は、配列内のインデックスを使用します.この部分がどういう意味か分かりません.
    1 2 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にあるやつだけを用いて無秩序pairを作成してカウントすることである)
    idx 1にいるやつを置きたいなら[1,4]を置くことができます.では同時に2つ入れると?dp[idx-1]に記録された値が含まれます.

    現在の配列のインデックス


    したがって,作成可能な配列のインデックスは1から自分のインデックスである.インデックスの合計を格納します.
    そうであれば、インデックスを記録する必要があります.そのため、私はあなたにディックシャナを作ってあげました.
    dickshernerに値がある場合は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))