rt，大致思路是从后往前贪心，线段树中每个叶子节点的值为“与当前位置的值相同的后一个位置”（如果当前位置从左点往右看不是第一次出现，则的值为 $0$）。

用线段树维护区间最大值，再暴力更新查询的区间，即当前区间的最大值作下一次查询的右端点。

如果中途出现某一个区间的最大值小于等于查询的右端点，则一定不合法（即某个一当前位置为左端点的“子数组”每个值都出现了两次以上，必须修改当前位置的值），否则当查询区间的右端点到达某一个修改过的位置或越界，则一定合法。

CF 上跑了五百多毫秒，但我无法证明每次“暴力修改查询区间”的最劣复杂度，感激不尽。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n,a[300005],t[1200005],ans,last;
set<int> st[300005];
priority_queue<pair<int,int> >q;
void push_up(int x)
{
	t[x]=max(t[x*2],t[x*2+1]);
	return;
}
void build(int x,int l,int r)
{
	t[x]=0;
	if(l==r)
	{
		return;
	}
	int mid=(l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	return;
}
void become(int x,int l,int r,int wz,int k)
{
	if(l>wz||r<wz)
	{
		return;
	}
	if(l==r)
	{
		t[x]=k;
		return;
	}
	int mid=(l+r)/2;
	become(x*2,l,mid,wz,k);
	become(x*2+1,mid+1,r,wz,k);
	push_up(x);
	return;
}
int ask(int x,int l,int r,int nl,int nr)
{
	if(l>nr||r<nl)
	{
		return 0;
	}
	if(nl<=l&&r<=nr)
	{
		return t[x];
	}
	int mid=(l+r)/2;
	return max(ask(x*2,l,mid,nl,nr),ask(x*2+1,mid+1,r,nl,nr));
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		ans=0;
		cin>>n;
		last=n+1;
		while(!q.empty())
		{
			q.pop();
		}
		for(int i=1;i<=n;i++)
		{
			st[i].clear();
		}
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
			st[a[i]].insert(i);
		}
		build(1,1,n);
		for(int i=n;i>=1;i--)
		{
			while(!q.empty())
			{
				pair<int,int> now=q.top();
				if(now.first>=i)
				{
					become(1,1,n,now.second,0);
					q.pop();
				}
				else
				{
					break;
				}
			}
			auto now=st[a[i]].upper_bound(i);
			if(now==st[a[i]].end())
			{
				become(1,1,n,i,n+1);
				auto lst=st[a[i]].lower_bound(i);
				if(lst!=st[a[i]].begin())
				{
					lst--;
					q.push({*lst,i});
				}
				else
				{
					last=i;
				}
				continue;
			}
			int wz=*now,p=*now;
			bool z=1;
			while(p<last)
			{
				int u=ask(1,1,n,i,p);
				if(u<=p)
				{
					z=0;
					break;
				}
				else
				{
					p=u;
				}
			}
			if(z==0)
			{
				ans++;
				become(1,1,n,i,n+1);
				last=i;
				st[a[i]].erase(i);
				continue;
			}
			auto lst=st[a[i]].lower_bound(i);
			if(lst==st[a[i]].begin())
			{
				become(1,1,n,i,wz-1);
			}
			else
			{
				lst--;
				become(1,1,n,i,wz-1);
				q.push({*lst,i});
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}