Treap with implicit keys
You should be giving your variables proper names. This would really improve the readability of your code. After all, code is read more times than it is written. As an outsider not all too well versed in advanced data structures, it's really hard to tell what k or v is supposed to be. Your code will effectively be self documenting if you change c and all other one character identifiers to something more reasonable like subtree_size or at least subsize. You won't need comments like /* left and right subtrees */.