自动搬运

查看原文

来自洛谷，原作者为

	xiaofu15191 Nothing.

搬运于2025-08-24 22:30:45，当前版本为作者最后更新于2024-07-31 16:19:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

今天模拟赛遇到的题目。第一眼看上去就像数据结构，可是不会打。以为是分块计数然后算之类的（虽然实际上也能用分块维护）。赛后弄了半天才想通。

首先我们设 $pre_i$ 为 $b_i$ 在数组中上一次出现的位置。

接着我们从前往后枚举变量 $r$，即我们要选的区间右端点。这个时候我们需要做到 $O(\log n)$ 来查询对于一个右端点的可行答案。

先考虑此时有哪些左端点可选。发现左端点只可能位于 $[pre_i+1,i-1]$ 中。那么就考虑怎么选中间的领队 $mid$。

回过头来，我们来看看枚举变量 $r$ 时每个元素如何影响答案。

首先，我们找到 $pre_r$，它不可以作为左端点更新答案了；同时，$[pre_{pre_r}+1,pre_r-1]$ 因为在 $r$ 出现了 $b_r$，这段区间中的 $b_i$ 不可以再作为中间点了。

因此，我们可以使用线段树维护答案，对于每个节点维护其区间内可作为左端点的数字个数 $lsum$，可作为中间点的数字个数 $midsum$ 以及对答案的贡献 $sum$。

枚举 $r$ 时，按照上面的步骤处理 $pre_r$，然后更新最终答案 $ans$；接着，$r$ 可作为左端点了，$[pre_i+1,r-1]$ 也可作为中间点了。

具体实现可见代码。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
long long n,num[200010],where[200010],pre[200010];
struct node
{
	long long l_num,mid_num,sum,lazy;
}tree[800010];
void pushup(long long now)
{
	tree[now].sum=tree[now<<1].sum+tree[now<<1|1].sum;
	tree[now].l_num=tree[now<<1].l_num+tree[now<<1|1].l_num;
	tree[now].mid_num=tree[now<<1].mid_num+tree[now<<1|1].mid_num;
}
void pushdown(long long now)
{
	tree[now<<1].lazy+=tree[now].lazy;
	tree[now<<1].mid_num+=tree[now].lazy;
	tree[now<<1].sum+=tree[now].lazy*tree[now<<1].l_num;
	tree[now<<1|1].lazy+=tree[now].lazy;
	tree[now<<1|1].mid_num+=tree[now].lazy;
	tree[now<<1|1].sum+=tree[now].lazy*tree[now<<1|1].l_num;
	tree[now].lazy=0;
}
void update_l(long long now,long long l,long long r,long long x,long long k)
{
	if(r<x||l>x) return;
	if(l==r)
	{
		tree[now].l_num+=k;
		tree[now].sum=tree[now].l_num*tree[now].mid_num;
		return;
	}
	pushdown(now);
	long long mid=(l+r)>>1;
	if(x<=mid) update_l(now<<1,l,mid,x,k);
	else update_l(now<<1|1,mid+1,r,x,k);
	pushup(now);
}
void update_mid(long long now,long long l,long long r,long long x,long long y,long long k)
{
	if(r<x||l>y) return;
	if(x<=l&&r<=y)
	{
		tree[now].mid_num+=k;
		tree[now].lazy+=k;
		tree[now].sum+=tree[now].l_num*k;
		return;
	}
	pushdown(now);
	long long mid=(l+r)>>1;
	if(x<=mid) update_mid(now<<1,l,mid,x,y,k);
	if(y>mid) update_mid(now<<1|1,mid+1,r,x,y,k);
	pushup(now);
}
long long query(long long now,long long l,long long r,long long x,long long y)
{
	if(r<x||l>y) return 0;
	if(x<=l&&r<=y) return tree[now].sum;
	pushdown(now);
	long long mid=(l+r)>>1,res=0;
	if(x<=mid) res+=query(now<<1,l,mid,x,y);
	if(y>mid) res+=query(now<<1|1,mid+1,r,x,y);
	return res;
}
int main()
{
	scanf("%lld",&n);
	for(long long i=1;i<=n;i++)
	{
		scanf("%lld",&num[i]);
		pre[i]=where[num[i]];
		where[num[i]]=i;
	}
	long long ans=0;
	for(long long i=1;i<=n;i++)
	{
		if(pre[i])
		{
			update_l(1,1,n,pre[i],-1);
			update_mid(1,1,n,pre[pre[i]]+1,pre[i]-1,-1);
		}
		ans+=query(1,1,n,pre[i]+1,i-1);
		update_l(1,1,n,i,1);
		update_mid(1,1,n,pre[i]+1,i-1,1);
	}
	printf("%lld\n",ans);
}