同じクエリが \(2\) つ以上あるとき、\(2\) 回目以降のクエリの答えは常に \(0\) となります。したがって、今までに存在したクエリを管理することで同じクエリは \(2\) つ以上存在しない場合に帰着されます。

このような帰着を行うと、各行および列に対してはじめその行や列に存在したゴミの番号および各ゴミが捨てられたか管理し、クエリが与えられたときには与えられた行や列にはじめ存在した各ゴミに対して愚直に捨てられているか判定する方法が十分高速です。

これは、はじめマス \((x, y)\) にあったゴミに対して \(x\) 行目に対応するクエリおよび \(y\) 列目に対応するクエリの \(2\) 回しか判定が行われないことからわかります。

各行および列に対してはじめその行や列に存在したゴミの番号を管理する列を作るのは \(O(H + W + N)\) 時間ででき、\(Q\) 個のクエリを合計 \(O(N + Q)\) 時間で処理できるため全体として時間計算量は \(O(H + W + N + Q)\) です。

実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
	int h, w, n;
	cin >> h >> w >> n;
	vector a(h + 1, vector<int>());
	vector b(w + 1, vector<int>());
	vector<bool> ux(h + 1), uy(w + 1); // 各行, 列にクエリが与えられたか
	vector<bool> used(n); // 各ゴミが捨てられたか
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(i);
		b[y].push_back(i);
	}
	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x;
			cin >> x;
			if (ux[x]) cout << 0 << '\n';
			else {
				int ans = 0;
				for (int e : a[x]) {
					if (!used[e]) {
						used[e] = true;
						ans++;
					}
				}
				ux[x] = true;
				cout << ans << '\n';
			}
		}
		else {
			int y;
			cin >> y;
			if (uy[y]) cout << 0 << '\n';
			else {
				int ans = 0;
				for (int e : b[y]) {
					if (!used[e]) {
						used[e] = true;
						ans++;
					}
				}
				uy[y] = true;
				cout << ans << '\n';
			}
		}
	}
}