题解：AT_abc366_c [ABC366C] Balls and Bag Query

n_ni · 2024-08-12 10:41:41 · 题解

题面

有一个空的袋子，现在要对它进行 N 次操作。

每个操作都是这样的：

• 1 x：将一个种类为 x 的球放入袋子里；
• 2 x：将一个种类为 x 的球从袋子里取出，保证执行此操作时袋子里有种类为 x 的球；
• 3：输出此时袋子里有几种球。

  数据范围

• 1 \leq Q \leq 2 \times 10^{5}
• 1 \leq x \leq 10^{6}

  思路

  最简单的思路：我们可以用数组存此时袋子里的球，如果要取出一个球就把他打上标记，遍历时不管它就好了。可是时间复杂度是 \O(N^2)，明显不能通过此题。

再看一眼数据范围：

• 1 \leq x \leq 10^{6}

这时就有了一个思路：桶。

我们让 f[i] 表示种类为 i 的球此时的数量，应对每个操作时只需：

• 1 x：f[i]++ ；
• 2 x：f[i]-- ；
• 3：（遍历一遍）？？？

很显然我们又遇到了一个问题：操作 3 怎么办？ 我们使用一个变量 sum 记录此时袋子里的球的种类数，这个问题基本上就解决了。但怎么维护这个变量呢？

维护方法：

• 操作 1：

  只有当这个种类的球没在袋子里时，sum 才需要加 1。

  所以就有了以下代码：

  if(f[x]==0)sum++;
  f[x]++;

• 操作 2：

  与刚才类似，只有将此球从袋子里取出后，袋子里没有此种类的球时，sum 才需要减 1。

  所以就有了以下代码：

  f[x]--;
  if(f[x]==0)sum--;

  复杂度分析

  时间复杂度：O(N)

  AC 代码

  
  #include<iostream>
  using namespace std;

int f[1000010];

int main(){ int n,sum=0; cin>>n; while(n--){ int op; cin>>op; if(op==1){ int x; cin>>x; if(f[x]==0)sum++; f[x]++; }else if(op==2){ int x; cin>>x; f[x]--; if(f[x]==0)sum--; }else{ cout<<sum<<endl; } } return 0; } // 就这么短吗？