Một bài sử dụng unordered_set hay

De bai:

A contiguous subarray is defined as unique if all the integers contained within it occur exactly once. There is a unique weight associated with each of the subarray. Unique weight for any subarray equals it's length if it's unique, 0 otherwise. Your task is to calculate the sum of unique weights of all the contiguous subarrays contained within a given array.
Input
First line of the input contains an integer T, denoting the number of testcases.
$2\ast T$ lines follow, where first line of each testcase contains an integer N denoting the number of integers in the given array. Last line of each testcase then contains N single space separated integers
Output
Print the summation of unique weights of all the subarrays for each testcase in a separate line.
Constraints

• $1\le T,N\le {10}^5$
• $0\le A_i\le {10}^9$
• Summation of N for all T does not exceed ${10}^5$

SAMPLE INPUT

1
5
1 2 3 4 5

SAMPLE OUTPUT

35

Explanation

Sample Case 1: Since, all integers are distinct within any contiguous subarray, therefore the unique weight will be the summation of lengths of all subarrays. Hence, this sums upto $5+4\ast 2+3\ast 3+2\ast 4+1\ast 5=35$

Time Limit:1,0 sec(s) for each input file.

Memory Limit:256 MB

Source Limit:1024 KB

Marking Scheme:Marks are awarded when all the testcases pass.

Allowed Languages:Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

Loi giai:

include<bits/stdc++.h>
using namespace std;
long long unsigned sum(int a[],int n){
 unordered_set<int> s;
 long long unsigned ans=0,j=0;
 for(int i=0;i<n;i++){
  while(j<n&& s.find(a[j])==s.end()){
   s.insert(a[j]);
   j++;
  }
  ans+=(j-i)*(j-i+1)/2;
  s.erase(a[i]);
 }
 return ans;
}
int main(){
 int t,i,n,j,a[1010101];
 cin>>t;
 while(t--){
  cin>>n;
  for(j=0;j<n;j++) cin>>a[j];
  cout<<sum(a,n)<<'\n';
 }
 return 0;
}