AT_abc347_e

题意

给定你一个长度为 \(n\) 且初始全部为 \(0\) 的序列 \(A\)，以及一个空集 \(S\)。接下来有 \(T\) 次操作，每次给定一个 \(x\)，若 \(x \in S\) 则将 \(x\) 删除，否则将 \(x\) 加入 \(S\)。在每次操作之后，对于 \(j=1,2,\cdots,n\)，若 \(j \in S\)，则给 \(a_j\) 加上 \(\left| S \right|\)，其中 \(\left| S \right|\) 定义为 \(S\) 的元素个数。所有操作完成后，求 \(A\) 的每一个元素的值。

思路

显然，对于 \(x \notin S\) 等价于它后面的每一个位置长度都加 \(1\)，\(x \in S\) 等价于后面的每一个位置长度都减 \(1\)。不难想到用差分来修改，再做一遍前缀和即可得到每一次操作做完后的 \(\left| S \right|\)。

接下来如何计算答案呢？读题可以发现，对于一个相同的 \(x\)，其一定在第奇数次出现时加入，第偶数次出现时删除。也就是说，在奇数次出现和偶数次出现这段时间内的 $ \sum \left| S \right|$ 是有效的，应计入答案。其余则无效，因为此时 \(x \notin S\)。

注意到要求的 \(\sum \left| S \right|\) 总是连续的，因此可以在前文的基础上再做一次前缀和，即可快速求得答案。

当然了，最后边界记得要处理。时间复杂度是 \(O(n)\) 的。

放上代码方便大家调试：

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long

using namespace std;


int n,m,x[1000001],a[1000001],s[1000001],pd[1000001],lst[1000001];

signed main()
{
	cin >> n >> m;
	for( int i = 1 ; i <= m ; i ++ )
	{
		cin >> x[i];
		if( pd[x[i]] ) s[i] --,pd[x[i]] = 0;
		else s[i] ++,pd[x[i]] = 1;
	}
	for( int i = 1 ; i <= m ; i ++ )
		s[i] += s[i - 1];
	for( int i = 1 ; i <= m ; i ++ )
		s[i] += s[i - 1];
	memset( pd , 0 , sizeof( pd ) );
	for( int i = 1 ; i <= m ; i ++ )
	{
		if( pd[x[i]] && lst[x[i]] ) a[x[i]] += s[i - 1] - s[lst[x[i]] - 1],pd[x[i]] = 0;
		else lst[x[i]] = i,pd[x[i]] = 1;
	}
	for( int i = 1 ; i <= m ; i ++ )
		if( pd[x[i]] )
			a[x[i]] += s[m] - s[lst[x[i]] - 1],pd[x[i]] = 0;
	for( int i = 1 ; i <= n ; i ++ )
		cout << a[i] << ' ';
	return 0;
}