Count on a Treap
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
In computer science, a treap is a binary search tree according to the keys and meanwhile a heap according to the weights. Follow the link for more details: http://en.wikipedia.org/wiki/Treap
Your task is to maintain a max-treap supporting the following operations:
- 0 k w: Insert a new node, whose key and weight are k and w.
- 1 k: Delete a node in the treap with key k.
- 2 ku kv: Return the distance between node u whose key is ku and node v whose key is kv.
No two nodes share the same key or the same weight in the tree, and we guarantee the node is indeed in the treap before a delete operation takes place.
The first line contains an integer N, the number of operations.
Each of the next N lines contains two or three integers "0 k w" "1 k" or "2 ku kv” . These integers describe the current operation.
For each distance query, print the distance between u and v.
- 1 ≤ N ≤ 200000
- 0 < k, w, ku, kv < 232
Input: 12 0 4 17535 0 10 38964 0 2 21626 0 1 61321 2 1 10 2 10 4 1 10 1 1 0 8 42634 2 8 4 2 8 2 2 4 2 Output: 1 2 2 1 1
|Tags||feb14, hard, segment-tree, treap, xiaodao|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.