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

Jian_ak5ac_simple · 2026-08-10 09:28:02 · 题解

诈骗题。

注意到初始都为 0，并且最多只会有 q 次加一，所以说减一的次数最多只会有 q 次，所以我们直接暴力维护非 0 的数的序列，然后对于操作二直接遍历序列减一，减完变成 0 就踢出序列，时间复杂度 O(q)。

代码如下：

#include<bits/stdc++.h>
#include<cmath>
#define fr(i,a,b) for(int i=(a);i<=(b);i++)
#define rf(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
#define pb push_back
#define mk make_pair
#define po pop_back
#define fi first
#define se second
using namespace std;
const int N = 5e5+2;
int n,qq;
int a[N],ans;
queue<int> q,p;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>qq;
    while(qq--){
        int op,x;
        cin>>op;
        if(op==1){
            cin>>x;
            if(a[x]==0)q.push(x);
            ans = ans^a[x]^(a[x]+1);
            a[x]++;
        }else{
            while(!q.empty()){
                ans = ans^a[q.front()]^(a[q.front()]-1),a[q.front()]--;
                if(a[q.front()])p.push(q.front());
                q.pop();
            }
            q = p;
            while(!p.empty())p.pop();

        }cout<<ans<<"\n";
    }
    return 0;
}
//cout<<"Yes";
//cout<<"No";