LOJ
这个题目挺有意思的，参考了一下题解写的。
设(fir[i])表示颜色(i)第一次出现的位置，(ed[i])表示颜色(i)最后一次出现的位置。
首先肯定可以转化为求区间([l,r])使得(fir[i]geq l, ed[i]leq r,iin [l,r])的个数
然后可以考虑枚举其中一个端点，计算另一个端点的个数。下面的部分就是参考题解的了。
我们首先枚举右端点(r)，考虑哪些端点不能选。
1、对于(ed[i]>r)的颜色(i)，显然([1,pos[i]])都不能选。（(pos[i])表示颜色(i)最近一次出现的位置）
2、对于(ed[i]leq r)的颜色(i)，就是((fir[i],ed[i]])不能选。
由于不能选的都是区间，然后我们可以写颗线段树，把不能选的位置计算一下。、
考虑到情况(1)在(r)增长的过程中，(pos[i])是单调递增的，我们可以用一个栈存下来，就可以快速找到那个位置了。
并且，对于情况(1)，我们并不需要在线段树中标记区间。
代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<set>
#include<bitset>
#include<map>
using namespace std;
#define rg register
#define int long long
void read(int &x){
char ch;bool ok;
for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;
for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;
}
const int maxn=3e5+10;
int T,n,m,a[maxn],f[maxn],ed[maxn],s[maxn*4],la[maxn*4];
int st[maxn],top,ans,id[maxn];
void update(int x){s[x]=s[x<<1]+s[x<<1|1];}
void build(int x,int l,int r){
s[x]=la[x]=0;if(l==r)return ;int mid=(l+r)>>1;
build(x<<1,l,mid),build(x<<1|1,mid+1,r);
}
void pushdown(int x,int l,int r,int mid){
la[x<<1]+=la[x],la[x<<1|1]+=la[x];
s[x<<1]=mid-l+1;s[x<<1|1]=r-mid;
la[x]=0;
}
void change(int x,int l,int r,int a,int b){
if(a<=l&&b>=r)return la[x]++,s[x]=r-l+1,void();
int mid=(l+r)>>1;if(la[x])pushdown(x,l,r,mid);
if(a<=mid)change(x<<1,l,mid,a,b);
if(b>mid)change(x<<1|1,mid+1,r,a,b);
update(x);
}
int get(int x,int l,int r,int a,int b){
if(a<=l&&b>=r)return s[x];
int mid=(l+r)>>1,ans=0;if(la[x])pushdown(x,l,r,mid);
if(a<=mid)ans+=get(x<<1,l,mid,a,b);
if(b>mid)ans+=get(x<<1|1,mid+1,r,a,b);
return ans;
}
signed main(){
read(T);
while(T--){
read(n);ans=0;build(1,1,n);
for(rg int i=1;i<=n;i++)read(a[i]);
for(rg int i=1;i<=n;i++){if(!f[a[i]])f[a[i]]=i;ed[a[i]]=i;}
for(rg int i=1;i<=n;i++){
if(i==ed[a[i]])change(1,1,n,f[a[i]]+1,i);
else st[++top]=a[i],id[top]=i;
while(top&&ed[st[top]]<=i)top--;
ans+=i-id[top]-get(1,1,n,id[top]+1,i);
}
printf("%lld
",ans);
for(rg int i=1;i<=n;i++)f[a[i]]=ed[a[i]]=0;
}
}