Catapult and Voodoo damage seems to be direct and instant HP damage and as mentioned can only be avoided with SoSa.
I did mention the Queen (it's not called Water Nymph) as a "fun" card, and that's basically what it is. That's not saying it can't be strong, just that it's unpredictable. If you're using this deck vs. Plat, the advice changes, and this is why it's very important to state the goal of the deck. Purify and Mirror Shield become very useful there, that's for sure.
Flying Titans require a lot of investment to get the most out of, and their strongest weapon being the Catapult, you can exploit that weakness to PC. While the 50 HP (which used to be 70 HP) makes it mostly impervious to killing CC, you can Antimatter (and Liquid Shadow), Freeze, Basilisk Blood, Reverse Time, Lobotomize (to remove Momentum) and Freeze+Shockwave (for instant kill) it. Flying weapons all have a huge weakness to the Eternity weapon since you can only pack 6 Animate Weapon (12 in Arena). While Catatitans is a strong PvP deck, it naturally gets a lot stronger in Arena with Dexterity, but it's not one of the dominant decks. It IS, however, one of the few decks a Timebow might have problems with if it's not packing Antimatter or manages to destroy the Catapults or Titans while they're in the weapon slot.
Happy to help.