ABC371E

問題

ABC371E

解法

種類数の扱いと，和の順序が鍵．

区間で有ることを忘れて，mlutiset $B$ を考える．
元 $x$ を固定すると，$x \in B$ になることは，
$x$ が $1$個以上含まれている事と同値．
よって，$B$ の種類数を数えるには，
$x$ の $B$ における multiplicity が 1以上かを判定すればよい．

実際には，multiplicity が 1以上である判定よりも，
complement をとって 0 である判定をした方が楽．

コード

main.cpp

int main() {
  ll n;
  cin >> n;
  vll a(n); rep(i,n) { cin >> a[i]; a[i]--; }

  vvll inds(n);// inds[x] is the sorted list of indices of x in a. 
  // rep(x,n) inds[x].push_back(-1);
  rep(i,n) inds[a[i]].push_back(i);
  rep(x,n) inds[x].push_back(n);

  ll ans = 0; 
  rep(x,n){
    ans += nC2(n+1);
    
    ll pre = -1; // index
    for(auto i: inds[x]){
      ans -= nC2(i - pre);
      pre = i;
    }
  }
  cout << ans << endl;

  return 0;
}