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

priority_queue1 · 2026-08-10 09:37:39 · 题解

个人感觉 C 是妙妙题。

首先，肯定不能每次修改之后 \mathcal{O}(N) 更新答案。注意到一个数异或两次同一个数值不变。那么对于查询 1 的更新即可做到 \mathcal{O}(1)。

来看查询 2。

考虑用一个数据结构来维护所有需要修改的值。发现删除与插入十分频繁，所以我们可以使用链表维护所有大于等于 1 的值。对于每一次更新，若当前值更新后为 0 则从链表中删除，更新方式与查询 1 相同。关于具体复杂度，不难发现查询 2 的时间复杂度与查询 1 相关。最多有 Q 次查询 1，所以查询 2 的单次最坏复杂度为 \mathcal{O}(Q)，均摊后为 \mathcal{O}(1)

整体我们用一个变量维护异或和。那么代码易得。

#include <iostream>
#include <list>
int n,a[500005]={},vis[500005],cnt=0,q;
int main(){
    std::list<int> lst;
    std::cin >> n >> q;
    while(q--){
        int op;
        std::cin >> op;
        if(op==1){
            int x;
            std::cin >> x;
            int t=a[x];
            a[x]++;
            cnt^=t;
            cnt^=a[x];
            if(t==0){
                lst.push_back(x);
            }
        }else{
            for(auto i=lst.begin();i!=lst.end();){
                int t=a[*i];
                a[*i]--;
                cnt^=t;
                cnt^=a[*i];
                if(!a[*i])i=lst.erase(i);
                else i++;
            }
        }std::cout << cnt << "\n";
    }
    return 0;
}

总复杂度 \mathcal{O}(N+Q)