AT_abc347_e 题解

很水。

一个 las 数组，记录 a[i] 这个数上一次被加入是什么时候。

注意，为防误判，在 a[i] 被删除的时候，将 las[a[i]] 设为 \(0\)。

你也可以这么理解：las 是记录在哪出现的 visit 数组。

每次加入一个数的时候，\(\left|S\right|\) 就加 \(1\)，并且使 las[a[i]] 等于 i。

删除时，\(\left|S\right|\) 减 \(1\)，统计这段区间内的答案，并且使 las[a[i]] 等于 \(0\)。

求一段区间内答案很好做，前缀和。

然后记得最后要看一下哪些数还在，记得也把他们的答案加上。

#include<stdio.h>
#include<bits/stdc++.h>
#define N 1000010
#define MOD 998244353
#define esp 1e-8
#define INF 999999999999999999
#define LL long long
#define rep(i,a,b,g) for(LL i=a;i<=b;i+=g)
#define rem(i,a,b,g) for(LL i=a;i>=b;i-=g)
#define repn(i,a,b,g) for(LL i=a;i<b;i+=g)
#define remn(i,a,b,g) for(LL i=a;i>b;i-=g)
#define pll pair<LL,LL>
#define mkp(x,y) make_pair(x,y)
#define i128 __int128
#define lowbit(x) ((x)&(-(x)))
#define lc (u<<1)
#define rc (u<<1|1)
using namespace std;
void read(i128 &x)
{
	i128 f=1;
	x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	x*=f;
}
void writing(i128 x)
{
	if(x>=10)writing(x/10);
	putchar(x%10+'0');
}
void write(i128 x)
{
	if(x<0)
	{
		cout<<'-';
		x=-x;
	}
	writing(x);
}
LL n,q,a[200010],las[200010],sum[200010],f[200010],ans;
int main()
{
	cin>>n>>q;
	rep(i,1,q,1)
	{
		cin>>a[i];
	}
	rep(i,1,q,1)
	{
		if(las[a[i]])
		{
			ans--;
			f[a[i]]+=sum[i-1]-sum[las[a[i]]-1];
			las[a[i]]=0;
		}
		else
		{
			ans++;
			las[a[i]]=i;
		}
		sum[i]=sum[i-1]+ans;
	}
	rep(i,1,n,1)
	{
		if(las[i])
		{
			f[i]+=sum[q]-sum[las[i]-1];
		}
	}
	rep(i,1,n,1)cout<<f[i]<<' ';
	return 0;
}