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++)