今晚 ABC C 题解

userId_undefined
Eucatastrophe‌🐛
出道萌新GESP6级时间刺客倔强青铜

2026-08-09 09:44:01

发布于：浙江

45阅读
0回复
0点赞

个人感觉 C 是妙妙题，为啥都不做 C 我感觉 C 比以往简单（？）

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

来看查询 22。

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

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

userId_undefined
去预览
0/2000

全部评论 9

热门讨论