Description&Data Constraint
农夫约翰合牛国（The United Cows of Farmer John，UCFJ）将要选派一个代表队参加国际牛学奥林匹克（International bOvine olympIad，IOI）。
有 \(N\) 头奶牛参加了代表队选拔。她们站成一行，奶牛 \(i\) 的品种为 \(b_i\)。
代表队将会由包含至少两头奶牛的连续区间组成——也就是说，对于满足 \(1\le l<r\le N\) 的奶牛 \(l\dots r\)。最边上的奶牛会被指定为领队。为了避免种内冲突，每一名领队都必须与代表队的其他成员（包括领队）品种不同。
请帮助 UCFJ 求出他们可以选派参加 IOI 的代表队的方法数。
\(1\le N \le 2\times 10^5\)。
Solution
自然的想法是枚举每个位置作为左端点，往后扩展，更新答案。
其实可以考虑遍历每个位置，求出以这个位置为右端点的方案数。
首先处理出每个数字上次出现的位置 \(last_i\)，那么对于右端点 \(i\)，合法的左端点只能在 \(last_i+1\) 到 \(i-1\) 中找。
当遍历到每个点时，我们令它的权值为 1，代表着这个点可以作为一种左端点的方案。
同时令它的上一个点的权值为 0，因为它无法再次成为左端点。
最后对于右端点 \(i\)，它的贡献就是 \(last_i+1\) 到 \(i-1\) 里 1 的个数。
单点修改，区间查询，随便搞个线段树或者树状数组即可。
时间复杂度 \(O(n\log n)\)?。
Code
#include<cstdio>
#define ll long long
#define N 200005
using namespace std;
int n,a[N],t[N],pre[N],tree[N<<2];
ll ans;
void modify(int now,int l,int r,int p,int v)
{
if (l==p&&r==p)
{
tree[now]=v;
return;
}
int mid=(l+r)>>1;
if (p<=mid) modify(now<<1,l,mid,p,v);
else modify(now<<1|1,mid+1,r,p,v);
tree[now]=tree[now<<1]+tree[now<<1|1];
}
int query(int now,int l,int r,int p,int q)
{
if (l>=p&&r<=q) return tree[now];
int mid=(l+r)>>1;
int res=0;
if (p<=mid) res+=query(now<<1,l,mid,p,q);
if (q>mid) res+=query(now<<1|1,mid+1,r,p,q);
return res;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (int i=1;i<=n;++i)
{
pre[i]=t[a[i]];
t[a[i]]=i;
}
for (int i=1;i<=n;++i)
{
modify(1,0,n,pre[i],0);
modify(1,0,n,i,1);
ans+=(ll)query(1,0,n,pre[i]+1,i);
}
printf("%lld\n",(ll)ans-n);
return 0;
}