这个题挺有意思的,他是要找连续的子序列,并且在子序列中唯一存在。这个就很有意思了,为什么呢? 先来看一下子序列的定义:
子序列是原来序列中的一部分序列,并且不一定连续。
所以题目要找连续的子序列,并且在子序列中唯一存在,这就说明了,这个连续子序列的左端点一定是从左往右第一个出现,并且右端点也是从右往左第一个出现,为什么这么说呢?
举个例子:
2 3 2 1 这个数组,2 1是一段连续的子序列,但是因为在整个序列中存在 2 1这个不连续的子序列,不满足了题意,所以一个连续子序列要想在子序列中唯一存在,他的左右端点一定都是第一个出现的。
我们使用map来记左右端点出现的次数就ok了。
然后就是对每一个第一次出现的左端点进行枚举,统计他右侧第一次出现的右端点,第一次出现的右端点的数目就是以这个左端点为首的连续且唯一的子序列的数量
这道题其实蛮有思维含量的,我脑子总是被绕晕,可能本来就比较迷糊,没读懂题目意思。
#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
typedef long long ll;
ll a[M];
map<ll,int> mpl,mpr;
int f[M];
int main(){
int t; cin>>t;
while(t--){
memset(f,0,sizeof(f));
mpl.clear(); mpr.clear();
int n; cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
mpl[a[i]]++;
if(mpl[a[i]]==1) f[i]=1;
else f[i]=0;
}
ll num=0;
ll sum=0;
for(int i=n;i>=1;i--){
mpr[a[i]]++;
if(mpr[a[i]]==1) num++;
if(f[i]) sum+=num;
}
cout<<sum<<endl;
}
return 0;
}