ABC347E 题解

KSCD_ · 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;
}