C. Sonya and Robots

• Quiz
  • https://codeforces.com/contest/1004/problem/C
• AC
  • https://codeforces.com/contest/1004/submission/98520055
• 解説
  • 左のロボットの居場所と右のロボットの居場所の切れ目をすべて見る
  • 左のロボットの領域を1つずつ拡大していく
  • すでに見た数字を左に取り込んだなら、そのペアはすでに数えているので数えない

sample 1

int main(){
    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    map<ll,ll> mp, mp2;
    
    // left
    mp[A[0]]++;

    // right
    FOR(i,1,N)mp2[A[i]]++;

    ll sum=0;
    sum += mp.size() * mp2.size();

    FOR(i,1,N-1){
      // i番目を左に移動
      ll a = A[i];
      bool new_val=false;
      if(mp.count(a)==0){
        new_val=true;
      }

      mp[a]++;
      mp2[a]--;
      if(mp2[a]==0){
        auto it = mp2.find(a);
        mp2.erase(it);
      }

      if(new_val){
        sum += mp2.size();
      }
    }
    p(sum);
    
    return 0;
}