题面翻译
给定数列 \(a\),定义一个子序列 \(S\) 是合法的当且仅当从 \(a\) 中有且仅有一种选法能选出子序列 \(S\)(选法相同定义为最终选出的位置集合相同)。
求其有多少非空合法子序列,满足它占据了 \(a\) 中一端连续的区间。
\(n\leq 10^5\)。
思路
判断区间合法性
对于一段区间\([l,r]\)而言,他合法,取决于\([1,l-1]\)不存在\(a_l\),并且\([r+1,n]\)不存在\(a_r\),也就是区间前面不能存在和左端点值一样的点,区间后面不能存在和右端点值一样的点。
证明图像如下
统计合法区间数
假设,我们当前点\(i\)为区间的左端点,那么从\([i,n]\)这个区间,有多少个点是可以作为右端点的呢?
在这里我们采用后缀和的思路。
设\(r[i]\)表示从\([r,n]\)的可以作为右端点的个数,假如说当前节点\(i\),从后往前是第一次出现的,那么\(r[i]=r[i-1]+1\),否则\(r[i]=r[i-1]\)
至于如何判断一个节点是否是从后往前第一次出现,我们使用map
就好了
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
int t,n,a[N],r[N];
map<int,bool> p,q;
inline void init()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--)
{
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
p.clear(),q.clear();//清空map
r[n+1]=0;//这是一个不用memset初始化的小技巧
for(int i=n; i; i--)//r[i]表示[i,n]可以作为区间结尾点的个数
{
r[i]=r[i+1]+(!q[a[i]]);
q[a[i]]=true;
}
long long ans=0;//用long long防止爆炸
for(int i=1; i<=n; i++)//枚举起始点
{
if (!p[a[i]])//如果当前这个点可以作为区间起始点
ans+=r[i];
p[a[i]]=true;
}
cout<<ans<<endl;
}
}
signed main()
{
init();
return 0;
}
- Codeforces Beautiful Round 905 Arecodeforces beautiful round 905 codeforces round 905 div codeforces报告round 905 codeforces round 1887 905 educational codeforces beautiful round codeforces round div2 905 题解codeforces round 905 beautiful 1883f are you beautiful you are so codeforces beautiful blanket c-the