Pagh's problem is a datastructure problem often used [1][2] when studying lower bounds in computer science named after Rasmus Pagh.
Mihai Pătrașcu was the first to give lower bounds for the problem.
[3] In 2021 it was shown that, given popular conjectures, the naive linear time algorithm is optimal.
We must accept updates of the following kind: Given a pointer to two subsets
, create a new subset
After each update, we must output whether the new subset is empty or not.