自动搬运

查看原文

来自洛谷，原作者为

	zy AFO

搬运于2025-08-24 22:30:43，当前版本为作者最后更新于2021-05-25 19:26:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

题目大意：

求区间 $[l,r]$ 的数的种类。

对于以i为开头的方案数，只要保证让结尾不等于这段区间的数字，也即让结尾是该数字靠前出现的位置。

代码实现

可以从 $n$ 到 $1$ 枚举开头。

不断更新靠前的位置。

• 树状数组维护种类

更改：

定义数组 $tre$e 表示种类数，当有一个新元素加入时，现将上一个位置上的种类数 -1，然后再让新加入的位置种类数 +1。

（一开始的位置可以设置成 $n+1$ ）

查询：

先前位置的前一个元素的种类数。

时间复杂度： $\mathcal{O}_{nlogn}$

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack> 
#define lowbit(x) x & -x;
#define int long long 
#define N 400010
using namespace std;
int re() {
	int p=0; char i=getchar();
	while(i<'0'||i>'9')	i=getchar();
	while(i>='0'&&i<='9')	p=p*10+i-'0',i=getchar();
	return p;
}
int n,ans;
int a[N],f[N];
int tree[N];
int ask(int x) {
	int sum=0;
	while(x>0) {
		sum+=tree[x];
		x-=lowbit(x);
	}
	return sum;
}
void add(int x,int k)
{
	while(x<=2*n) {
		tree[x]+=k;
		x+=lowbit(x);
	}	
}
signed main()
{
	n=re();
	for(int i=1;i<=n;i++) {
		a[i]=re();
		f[i]=n+1;
	}
	for(int i=n;i>=1;i--)
	{
		ans+=ask(f[a[i]]-1);
		add(f[a[i]],-1);
		f[a[i]]=i;
		add(f[a[i]],1);
	}
	cout<<ans<<endl;
}

如有不妥，请不要吝啬您的评论。

$qwq$

双倍经验

三倍经验