【USACO 2021 US Open, Gold】United Cows of Farmer John 题解

【USACO 2021 US Open, Gold】United Cows of Farmer John

Description

Input

Output

输出可能的代表队的数量。

Sample Input

7
1 2 3 4 3 2 5

Sample Output

13

Data Constraint

题解

仔细阅读题目，我们可以发现其实可以把题目转化一下
假设b[i](是队头的领队，在合法的情况下，这个队列是不能有其他等于)b[i](的数的，也就是说，最多可以延伸到数字)b[i](上一个出现的位置减一 那么这个题目就变成了数一段区间有多少种数字的问题了 设)last[i](表示数字)i(上一个出现的位置（初值赋值为)n+1(即可） 从)nsim1(扫，找出)b[i](与)last[b[i]]-1(之间有多少个合法的数字（关于队尾的领队在之前就会处理过），将)last[b[i]](的值删除（因为队尾的领队也不能和队伍中的其他的数一样），然后更新)last[b[i]]$的值，再插入这个位置
然后我们可以发现其中的操作是只有单点修改，区间查询，所以随便用个线段树或者树状数组写写就行了（本人写的是线段树）
其实这题还可以无脑套主席树模板，但是我不会

CODE

#include<cstdio>
#include<string>
#define R register int
#define N 200005
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
int n,last[N],b[N];
ll tree[N<<2],ans;
int max(int a,int b) {return a>b?a:b;}
int min(int a,int b) {return a<b?a:b;}
void read(int &x)
{
	x=0;int f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
ll sum(int u,int l,int r,int x,int y)
{
	if (l>=x && r<=y) return tree[u];
	int mid=l+r>>1;ll res=0;
	if (x<=mid) res+=sum(u<<1,l,mid,x,y);if (y>mid) res+=sum(u<<1|1,mid+1,r,x,y);
	return res;
}
void ins(int u,int l,int r,int k,int x)
{
	if (l==r) {tree[u]+=x;return;}
	int mid=l+r>>1;
	if (k<=mid) ins(u<<1,l,mid,k,x);else ins(u<<1|1,mid+1,r,k,x);
	tree[u]=tree[u<<1]+tree[u<<1|1];
}
int main()
{
	read(n);
	for (R i=1;i<=n;++i) read(b[i]),last[i]=n+1;
	for (R i=n;i;--i)
	{
		ans+=sum(1,1,n+1,1,last[b[i]]-1);
		ins(1,1,n+1,last[b[i]],-1);
		last[b[i]]=i;ins(1,1,n+1,i,1);
	}
	printf("%lld
",ans);
 	return 0;
}