题解

解这道题首先要知道一些异或的小知识
1.$a\bigoplus b = b \bigoplus a$ 很简单，就是交换律，三个及以上都一样
2.$a \bigoplus a=0$
3.$a \bigoplus 0=a$
根据性质2可以知道重复异或一个数相当于在异或和里删去了这个数，所以更新异或和就可以先异或旧值，更新旧值后再异或新值
根据性质3可以知道，一个数异或0是不变的，所以如果$A_i$是0就不用重复计算，可以用一个数组来记录$\geq0$的元素下标
这样操作2的时间复杂度就省下来了

#include<iostream>
#include<set>
#include<vector>
using namespace std;
int n,q;
int main(){
    cin>>n>>q;
    vector<int>a(n+1,0);
    set<int>st;//记录a中>=1的元素的下标
    int ans=0;//异或和
    while(q--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            ans^=a[x];
            a[x]++;
            ans^=a[x];
            if(a[x]>=1)st.insert(x);
        }else {
            vector<int>t;//记录进行了操作2的元素的下标
            for(auto it : st){
                ans^=a[it];
                a[it]--;
                ans^=a[it];
                t.push_back(it);
            }
            //删除变成0的元素的下标
            for(auto it : t){
                if(a[it]==0)
                    st.erase(it);
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}