题解：AT_abc470_c [ABC470C] Inc, Dec, Xor

· · 题解

Problem

给定一个长度为 N、初始值全部为 0 的整数序列 A，并对其进行 Q 次操作，操作分为两种：

每次操作后，要求输出 A 数组的按位异或值。

Solution

题外：赛时一直在考虑拆成二进制，但是一直解决不了操作 2，被卡到差点没做出来。这大抵是 ABC 最难的 C 题了罢。

不难发现，只有进行过操作 1 的 i，操作 2 才能对其造成影响，而操作 1 的次数不会太多。如果我们能统计现在满足 A_i > 0 的 i，操作 2 时就可以只把这些 i 上的元素减 1，如果减到了 0 就把这个 i 删除，就可以保证算法的高效性。STL 的 set 就很满足我们的需要，既可以去重，又可以删除。

为了能快速统计答案，我们需要利用一个定理：任意一个整数疑异或其本身得到的值一定为 0，任意一个整数异或 0 等于这个整数本身。所以只需要在加入元素时异或新元素，删除元素时异或这个元素，就可以更新答案。

复杂度分析：因为操作 1 的次数不可能超过 Q，满足 A_i 大于 0 的 A_i 之和也不可能超过 Q，所以时间复杂度不会超过 O(2Q \log N)，也就是均摊 O(Q \log N)，完全可以跑完。

Code

AC 记录

#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
const int N=500005,M=21;
int n,q,op,x,a[N];
set<int> st;
int main(){
    scanf("%d%d",&n,&q);
    int ans=0;
    for(;q--;){
        scanf("%d",&op);
        if(op==1){
            scanf("%d",&x);
            ans^=a[x];//删除旧值
            a[x]++;
            ans^=a[x];//加入新值
            st.insert(x);
        }
        else{
            for(set<int>::iterator it=st.begin();it!=st.end();){
                int x=(*it);
                ans^=a[x];
                a[x]--;
                ans^=a[x];
                if(!a[*it])//一定要把没用的元素删掉！不然会很容易TLE掉的
                    it=st.erase(it);//在C++11之后，STL中erase函数会返回删除该值之后下一个值的指针
                else
                    ++it;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}