CF1888C You Are So Beautiful 题解
考虑什么样的元素才可以成为区间的左 / 右端点。以左端点为例：当且仅当在它左边没有与它相等的元素，它才可能成为左端点。证明考虑充分性和必要性，一方面如果它左边有与它相等的元素，那么将“子序列”的端点移到左边那个元素，子序列的所有元素的值也不会变；另一方面，因为判断的是整个连续的子段，假设一个非端点元素移动了，那么它与端点元素的相对位置就会改变，而又已知左端点的左边不可能有与它相等的元素（右端点同理），所以它一移动这个序列必然会改变。
预处理出所有备选的左端点和右端点（使用 STL map；别用 unordered_map，昨晚房间里面有个人用这个被叉了），装进两个数组，然后枚举左端点，用 lower_bound 来匹配可用的右端点，统计方案总和即可。
放代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t; cin>>t;
while(t--){
int n,c=0; cin>>n;
vector<int> a(n),l,r;
for(auto &i:a)cin>>i;
map<int,bool> m,m2;
for(int i=0;i<n;i++)
if(!m[a[i]])m[a[i]]=true,l.emplace_back(i);
for(int i=n-1;~i;i--)
if(!m2[a[i]])m2[a[i]]=true,r.emplace_back(i);
// 即第一次出现的，左端点的从左往右扫，右端点从右往左扫
reverse(r.begin(),r.end());
for(int i:l)c+=r.size()-(lower_bound(r.begin(),r.end(),i)-r.begin());
// 统计答案
cout<<c<<'\n';
}
return 0;
}