题解：AT_abc366_c [ABC366C] Balls and Bag Query

· · 题解

题解：AT_abc366_c [ABC366C]

前言

题目已经翻译好了，故不提供翻译解释。

更好的阅读体验？

正解

需注意：编号为 x 的球可以有很多个，赛场上因此痛吃罚时。

考虑到 x\in [1,10^6]，数据范围较小，故开一个桶：s_x 记录 x 出现的次数。

同时维护一个集合，记录目前还存在的球种类。考虑到我们只关心球种类的数量，故可将集合变为一个计数器。

代码很容易写出来。

时间复杂度 O(Q)，空间复杂度 O(\max x)。

加强版

但是如果 1\leq x \leq 10^{18}，那 x 肯定无法用桶去装了。这是因为数组一定是连续的，而事实证明根本不需要连续，因为很多数是没有出现过的。

但是 C++ 中的 STL 恰恰有这么一个非连续的数据结构 map。其使用方法与数组类似。

注意：map 在没有修改的键值对应值默认是 0，这里只举整数类型为例。

#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)

using namespace std;
typedef long long ll;
typedef double db;

int Q,cnt=0;
map<ll,ll> s;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    cin>>Q;
    while(Q--)
    {
        int o;ll x;
        cin>>o;
        if(o==1)
        {
            cin>>x;
            if(s[x]==0) cnt++;
            s[x]++;
        }
        if(o==2)
        {
            cin>>x;
            s[x]--;
            if(s[x]==0) cnt--;
        }
        if(o==3)
            cout<<cnt<<endl;
    }
}

时间复杂度为 O(Q\log Q)。因为 map 一次查询的复杂度是 O(Q\log Q) 的，且最多有 Q 个球会加入袋子。

空间复杂度 O(Q)，理由同上。

总结

这道题作为 C 还是很水的，而且不必用 STL。

AC：https://atcoder.jp/contests/abc366/submissions/56635007

广告

安利一下我的代码仓库。AtCoder 的部分题目代码即调试信息、避坑可以在这里找到。