题解 | #链式边权#

#include <iostream>
#include <unordered_map>
using namespace std;

int nums[100005];

void solve(int n) {
    long long pre = 0;
    unordered_map<int, int> left, right;
    // 初始时所有点都在右侧
    for (int i = n - 1; i >= 0; --i)
        right[nums[i]]++;
        
    // 计算每条边的权值
    for (int i = 0; i < n - 1; ++i) {
        // 计算当前边的权值并输出
        printf("%lld%c", pre += n - 2 * i - right[nums[i]] + left[nums[i]], 
               i == n - 2 ? '\n' : ' ');
        // 将当前点从右侧移到左侧
        right[nums[i]]--;
        left[nums[i]]++;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &nums[i]);
    solve(n);
    return 0;
}

import java.util.*;

public class Main {
    public static void solve(int n, int[] nums) {
        long pre = 0;
        Map<Integer, Integer> left = new HashMap<>();
        Map<Integer, Integer> right = new HashMap<>();
        
        // 初始时所有点都在右侧
        for (int i = n - 1; i >= 0; i--) {
            right.put(nums[i], right.getOrDefault(nums[i], 0) + 1);
        }
        
        // 计算每条边的权值
        for (int i = 0; i < n - 1; i++) {
            pre += n - 2 * i - right.getOrDefault(nums[i], 0) + 
                   left.getOrDefault(nums[i], 0);
            System.out.print(pre + (i == n - 2 ? "\n" : " "));
            
            // 将当前点从右侧移到左侧
            right.put(nums[i], right.get(nums[i]) - 1);
            left.put(nums[i], left.getOrDefault(nums[i], 0) + 1);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        solve(n, nums);
    }
}

def solve(n, nums):
    pre = 0
    left = {}
    right = {}
    
    # 初始时所有点都在右侧
    for x in nums:
        right[x] = right.get(x, 0) + 1
    
    # 计算每条边的权值
    for i in range(n-1):
        pre += n - 2 * i - right.get(nums[i], 0) + left.get(nums[i], 0)
        print(pre, end='\n' if i == n-2 else ' ')
        
        # 将当前点从右侧移到左侧
        right[nums[i]] -= 1
        left[nums[i]] = left.get(nums[i], 0) + 1

n = int(input())
nums = list(map(int, input().split()))
solve(n, nums)