クエリ \(1\) と \(3\) のみがある場合

各ユーザ \(X\) について，ユーザ \(X\) が閲覧できるコンテストページの集合を \(S_X\) とします．クエリ \(1\) では，\(S_X\) に \(Y\) を追加します．クエリ \(3\) では，\(S_X\) に \(Y\) が含まれているかどうか判定すればよいです．

\(S_X\) の要素数は最大で \(M\) 個になるため，\(S_X\) を配列を使って管理した場合，\(S_X\) に \(Y\) が含まれているかの判定にクエリあたり \(O(M)\) 時間かかります．よって，時間計算量は全体で \(O(QM)\) となり，実行時間制限に間に合いません．

そこで，集合を効率的に管理するデータ構造を用いる必要があります．そのようなデータ構造はほとんどの言語で標準機能として提供されており，C++ と Python では set として利用することができます．set を使った場合，クエリ \(1\) とクエリ \(3\) の処理をクエリあたり \(O(\log M)\) 時間で行うことができます．全体の時間計算量は \(O(Q \log M)\) となり，十分高速です．

クエリ \(2\) もある場合

クエリ \(2\) において，\(1\) から \(M\) をすべて \(S_X\) に追加してしまうと，クエリあたり \(O(M \log M)\) の時間がかかり，非効率的です．そこで，ユーザ \(X\) がすべてのページを閲覧できるかどうかのフラグ \(f_X\) を管理しておきます．すると，クエリ \(2\) の処理は \(f_X\) を \(\mathrm{true}\) に設定するだけでクエリあたり \(O(1)\) 時間になります．

このとき，クエリ \(3\) の処理は以下のように修正されます．

• \(f_X=\mathrm{true}\) ならば，ユーザ \(X\) はすべてのコンテストページを閲覧できるので， Yes を出力する
• そうでないとき，\(S_X\) に \(Y\) が含まれているならば Yes を，そうでないならば No を出力する．

実装例 (C++)

実装例 (Python)