本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 11:16:22

题意

初始有一个长度为 $N$，元素均为 $0$ 的数组 $A$ 和一个空集合 $S$。进行 $Q$ 次操作，每次给出一个数 $x$，若其不在 $S$ 中则加入 $S$，否则将其从 $S$ 中删除。之后给 $A$ 中下标在 $S$ 中的元素各加上 $\left|S\right|$，$\left|S\right|$ 为 $S$ 中的元素个数。求最终的 $A$ 数组。

思路

如果暴力修改，复杂度为 $O(N^2)$，无法通过本题。

因此考虑分别处理 $A$ 的每一位。对于每一个下标，都会在其第 $(2k-1)$ 次和第 $2k$ 次被操作之间被加上数，那么就可以把最终答案变为若干个区间的和。

那么记录下所有操作时的 $\left|S\right|$ 并求前缀和，对于 $A$ 中每一位分别操作即可。

这样时间复杂度优化至 $O(N)$，可以通过本题。

代码

#include<iostream>
#include<vector>
#define int long long
const int N=2e5+10;
using namespace std;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int n,Q,cnt,s[N];\/\/cnt为目前S中元素个数，s为前缀和数组 
bool f[N];\/\/每个下标是否在S中 
vector <int> pos[N];\/\/每个下标出现的位置 
signed main()
{
	n=read(),Q=read();
	for(int i=1;i<=Q;i++)
	{
		int t=read();
		if(!f[t]) cnt++,f[t]=1;
		else cnt--,f[t]=0;
		s[i]=s[i-1]+cnt;
		pos[t].push_back(i); 
	} 
	for(int i=1;i<=n;i++)
	{
		int t=0;\/\/分别处理每一位 
		if(pos[i].size()%2) pos[i].push_back(Q+1);\/\/如果出现奇数次，则操作结束时其还在序列中，需要特判 
		for(int j=0;j<pos[i].size();j+=2)
		{
			int l=pos[i][j],r=pos[i][j+1]-1;
			t+=s[r]-s[l-1];
		}\/\/每两次之间都能取得贡献 
		cout<<t<<' ';
	}
	return 0;
}