AT_abc366_c [ABC366C] Balls and Bag Query 题解

Snowflake_Fairy · 2024-08-12 13:26:29 · 题解

解题思路

此题有 3 种操作，分别是插入、删除、询问。

其实我们不需要进行实质的操作，我们只需要表示出这个操作即可。然后我们就很容易地想到桶。

我们设桶数组为 a，询问答案为 ans。

对于插入一个数 x，我们只需要 a_x + 1 就可以说明这个数已经保存下来了，如果这时 a_x = 1，说明 x 已经出现了，ans + 1，需要注意的是，我们不能因为 a_x > 0 然后 ans + 1，因为这样会重复统计。

对于删除一个数 x，我们只需要 a_x - 1 就可以说明这个数已经删除了，如果这时 a_x = 0，说明 x 已经删除完了，这时 ans - 1。

对于询问我们保存的数中不同的数的个数，打印 ans 即可。

这里由于作者习惯使用 map 容器进行桶操作，所以代码给出的是 map 容器版，如果使用普通数组也是同样的方法。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
map<int, int> m;
int ans = 0;
signed main() {
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int q;
    cin >> q;
    while (q--) {
        int flag;
        cin >> flag;
        if (flag == 1) {
            int x;
            cin >> x;
            m[x]++;
            if (m[x] == 1)
                ans++;
        } else if (flag == 2) {
            int x;
            cin >> x;
            m[x]--;
            if (m[x] == 0)
                ans--;
        } else {
            cout << ans << "\n";
        }
    }
    return 0;
}