Problem: You have some sets and you want to check if set $$$B$$$ is subset of set $$$A$$$. You can erase or insert any element from any set. Let's say that $$$Q$$$ is the number of queries (check,insert or erase) and $$$Q <= 10^5$$$.
I think that may exist a solution using hash function. If you find the binary representation of all the sets (a bit is true only if it exists in the set) if there is a way to find the bitwise AND operation of two hash numbers then if $$$A$$$ & $$$B$$$ $$$=$$$ $$$B$$$ then $$$B$$$ is subset of $$$A$$$.
Any ideas about a solution?
Lets mantain three sets:
oa — numbers only in A
ob — numbers only in B
oab — numbers in A and B
Check is equal to ob.empty()
Also it is easy to mantain sets after insert/delete
How can this work if there are more than 2 sets?
Assuming you have empty sets at first. For sets with >= X values, we maintain them in large boolean arrays and also maintain their pairwise oa ob oab thing. For small sets, we maintain the sorted values in there. So we can solve small-small and small-large in O(X) and large-large in O(1) using O(X*Q) memory and O(X) O(Q/X) time per small/large update. Make X = sqrt(Q) and we get O(sqrt(Q)) per update.
You could try to do sqrt decomposition: If $$$B$$$ has a size smaller than $$$O(\sqrt{Q})$$$, then check in $$$O(B)$$$. Otherwise, there are at most $$$O(\sqrt{Q})$$$ different options for $$$A$$$ (I assume you check in the beginning that $$$|A| \geq |B|$$$), yielding $$$O(Q)$$$ pairs in total. Have the answer (more specifically, $$$|B \setminus A|$$$) precomputed for all $$$O(Q)$$$ pairs. Overall solution would be $$$O(Q \sqrt{Q})$$$, if you keep all sets stored as (sparse) hash sets. Better complexities might exist, though.