C. You Are So Beautiful Codeforces Round 905 (Div. 2)

Problem - C - Codeforces

题目大意：有一个长度为n的数组a，问有多少个子串[l,r]，满足这个子串作为子序列只在a中出现过一次

1<=n<=1e5;1<=a[i]<=1e9

思路：我们发现对于从1开始的连续区间，答案都是非递减的，所以我们考察每添加一个数字，答案怎么变化，并不会影响前面的答案。

        那么假如我们当前新添了一个数a[r]，那么新增的合法答案计数就是a[r]为区间右端点的合法子串，也就是看1到r中有多少个l满足[l,r]是合法区间，我们发现，对于前面的一个数a[i]，如果它出现了多次，那么只有第一次出现时作为区间左端点才是合法的，在后面出现时那个数都可以被第一次出现的那个数替代，所以每个位置的数的贡献也就是在它前面第一次出现的数的数量，那么每个相同的数的贡献，也就是在最后出现的那个位置之前有多少第一次出现的数。

        要统计答案我们首先记录每个数最后一次出现的位置las[i]，然后从左往右遍历数组，记录第一次出现的数的数量，然后如果当前数已经在这个数最后一次出现的位置，就统计这个数的贡献。

//#include<__msvc_all_public_headers.hpp>
#include
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 5;
int n;
int a[N];
void init()
{
	
}
void solve()
{
	map<int, int>las;
	cin >> n;
	init();
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		las[a[i]] = i;//记录每个数字最后一次出现的次数
	}
	ll ans = 0;
	ll cnt = 0;
	set<int>vis;
	for (int i = 1; i <= n; i++)
	{		
		if (vis.find(a[i]) == vis.end())
		{//第一次出现这个数字
			cnt++;//记录有多少个第一次出现的
			vis.insert(a[i]);
		}
		if (las[a[i]] == i)
		{//当前数字是最后一次出现的位置，统计贡献
			ans += cnt;
		}
	}
	cout << ans;
	cout << '\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	//t = 1;
	while (t--)
	{
		solve();
	}
	return 0;
}