Algorithm to Bulk Delete nodes from a Treap
Section 2 of the original treaps paper ("Randomized Search Trees" by Aradon and Seidel), as well as the journal version of the same paper (also called "Randomized Search Trees"), explains how to split and join treaps without affecting the validity of the randomized balancing. That's all you need to bulk delete.


  In order to split a treap storing $X$ according to some $a$, simply insert an item with key $a$ and "infinite" priority. 
  By the heap-order property the newly inserted item will be at the root of the new treap.
  By the in-order property the left subtree of the root will be a treap for $X_1$ and the right subtree will be a treap for $X_2$.
  In order to join the treaps of two sets $X_1$ and $X_2$ as above, simply create a dummy root whose left subtree is a treap for $X_1$ and whose right subtree is a treap for $X_2$, and perform a delete operation on the dummy root.