B - COUNTries

キーワード

必要な情報の精査

解説

「どの国が存在し，どの国が存在しないのか」という情報を管理しようとすると，$N = 10^{18}$ 程度の $N$ では一般的にメモリを確保できません。
そこで出力が求められるクエリ$3$に注目すると，国の数を答えなければならないので，「現時点で存在する国の数」という情報が必要であり，「どの国が存在し，どの国が存在しないのか」という情報を保持しておく必要はありません。
よって，現時点の国の数を管理しておき，クエリ $1,2$ での増減を考えれば良いです。

具体的には，現時点の国の数を $C$ とすると，はじめは $C = N$ です。
クエリ $1$ では，国が $2$ つ無くなり，新たに $1$ つ建国されるので，$C$ を $1$ 減らします。
クエリ $2$ では，国が $1$ つ無くなり，新たに $2$ つ建国されるので，$C$ を $1$ 増やします。
このようにクエリ $1,2$ では処理を行い，クエリ $3$ ではその時点の $C$ を出力すれば良いです。

実装例(C++)

xxxxxxxxxx

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

​

int main() {

  ll n; int q; cin >> n >> q;

​

  ll cnt = n;

  for(int i = 0; i < q; i++) {

    int c; cin >> c;

​

    if(c == 1) {

      // クエリ1

      ll dummy; cin >> dummy >> dummy;

      cnt--;

    }else if(c == 2) {

      // クエリ2

      ll dummy; cin >> dummy;

      cnt++;

    }else{

      // クエリ3

      cout << cnt << '\n';

    }

  }

​

  return 0;

}