AtCoder Beginner Contest 347 E

https://atcoder.jp/contests/abc347/tasks/abc347_e

時系列でSの大きさを記録します。実際には累積和をVecにします。

// Set Add Query
#![allow(non_snake_case)]

use std::collections::HashMap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<usize>) {
    let v = read_vec();
    let N = v[0];
    let X_: Vec<usize> = read_vec();
    let X: Vec<usize> = X_.into_iter().map(|x| x - 1).collect();
    (N, X)
}

fn F(N: usize, X: Vec<usize>) -> Vec<usize> {
    let mut A: Vec<usize> = vec![0; N];
    let mut acc: Vec<usize> = vec![0];
    let mut dic: HashMap<usize, usize> = HashMap::new();
    for (p, x) in X.into_iter().enumerate() {
        if dic.contains_key(&x) {
            let q = dic.get(&x).unwrap();
            A[x] += acc[p] - acc[*q];
            dic.remove(&x);
        }
        else {
            dic.insert(x, p);
        }
        acc.push(acc.last().unwrap() + dic.len())
    }
    
    for (x, p) in dic.into_iter() {
        A[x] += acc.last().unwrap() - acc[p]
    }
    A
}

fn main() {
    let (N, X) = read_input();
    let A = F(N, X);
    println!("{}", A.into_iter().map(|a| a.to_string()).
                                    collect::<Vec<_>>().join(" "))
}