**Hint 1: Từ Brute Force(xét tất cả các tập con xuất từ $i$) hãy cố gắng tối ưu giảm số tập cần xét.**<br>
**Hint 2**: *Từ Hint 1, ta tìm được tất cả các bộ $i,j$ thỏa mãn trong đpt $O(n):$*<br>
*- Nếu chạy $j$ đến phần tử nào mà đã xuất hiện từ $i->j-1$ thì ngắt vòng, đến i+1 chỉ cần*<br>
*xét phần tử từ $j$ trở đi vì $i->j-1$ thỏa mãn thì $i+1->j-1$ cũng thỏa mãn.*<br>
*Do đó ta sẽ tạo $2$ con trỏ $i,j.$ Nếu $a[j]$ thỏa mãn thì $j++,$ còn $a[j]$ không thỏa mãn thì $i++.$*<br>
$->$ **Công thức giúp đếm số dãy khi biết tất cả các dãy thỏa mãn bắt đầu từ các vị trí $i?$**<br>
#**HƯỚNG DẪN:**<br>
+ Tạo $2$ con trỏ $i,j$ như hint $1$.<br>
+ Để tránh đếm trùng nhau, ta sẽ đếm lần lượt số lượng dãy con xuất phát từ $1..n$ thay vì đếm lung tung không theo trật tự.<br>
+ Nếu $a[j]$ thỏa mãn, thì tức là ta có thêm $1$ dãy mới xuất phát từ $i,$ nên $ans++.$<br>
+ Nếu $a[j]$ không thỏa mãn, ta tăng $i$ lên, đồng thời đếm tất cả các dãy thỏa mãn từ $i->(j-1). J$ chưa tăng để xét đến vòng lặp sau.<br>
+ Khi cộng $j$ đến giá trị $n,$ tức là ta dừng vòng lặp, khi đó dãy $(i+1)->j-1$ thỏa mãn nhưng chưa được cộng vào.<br>
Ta cộng các dãy còn lại:<br>
$((j-1)-(i+1)+1)+((j-1)-(i+2)+1)+....+1$<br>
$= (j-i-1) + (j-i-2) +...+1$<br>
$= (j-i-1+1)\*(j-i-1)/2$<br>
$= (j-i)\*(j-i-1)/2$<br>
##**CODE MẪU:**<br>
```cpp
#include<iostream>
#include<map>
using namespace std;
map<int,int> mp;
long long n,a[100005],ans=0;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int i=0,j=0;
while(j<n)
{
if(mp[a[j]]==1)
{
mp[a[i]]--;
i++;
ans+=j-i;
}
else
{
ans++;
mp[a[j]]++;
j++;
}
}
ans+=(j-i)*(j-i-1)/2;
cout<<ans;
}
```
sharinganvanhoadong
Created at
2 likes