If there are two identical queries, the latter’s answer is always \(0\). Thus, by managing the already appeared queries, one may assume that there are no repeated queries.

Under this assumption, the following algorithm is fast enough: initially, enumerate the indices of trash placed in each row and column. Maintain whether each trash is removed or not. Given a query, inspect each trash in the given row or column by accessing the list of trash defined above, and check if the trash is flagged removed.

This is fast enough because, for a piece of trash initially placed at cell \((x, y)\), the trash is only inspected twice, for a query for row \(x\) and one for column \(y\).

Constructing the list of trash for each column and row costs \(O(H + W + N)\) time, and the \(Q\) queries can be processed in \(O(N + Q)\) time. Thus, the total computational complexity is \(O(H + W + N + Q)\).

Sample code

#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); // Whether the query for each row or column is already given
	vector<bool> used(n); // Whether each trash is already removed
	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';
			}
		}
	}
}