TREAP  Yet another range difference query!
Given an empty set S, you have to apply Q operations on this set while keeping the set sorted in increasing order and elements have indices 0 <= i < size(S)
The operations are insert, delete, find min difference in a given range, find max difference in a given range.
Input
I k : Insert k into S, if k is not in S
D k : Delete k from S, if k is in S
N i j : Print min{abs(S[x]  S[y])  i <= x, y <= j} or 1 if the range has 1 element
X i j : Print max{abs(S[x]  S[y])  i <= x, y <= j} or 1 if the range has 1 element
limits: 0 < Q <= 200000 , 0 <= k <= 10^9 , 0 <= i,j < size(S)
Output
For each N and X operations, print an integer per line as described above.
Example
Input: 11 I 1 I 12 I 4 I 8 N 0 3 X 0 3 N 1 3 X 0 2 D 4 N 0 1 X 1 2 Output: 3 11 4 7 7 4
hide comments
jusbut1943:
20180831 11:16:01
Why my solution is black, and shows 0K, Result: 0. 

fz0718:
20170722 23:10:28
Another fun BBST problem, that you also need lazy propagation for: https://csacademy.com/contest/archive/task/strings/ 

mahmud2690:
20160525 13:30:54
Why my solution is black, and shows 0K, Result: 0. 

timonknigge:
20150831 15:20:40
It might be worth pointing out that for the N query, we also require that x =/= y. 

bicsi:
20150702 23:38:35
This was probably the most resourceful problem I have ever coded! However, it was worth it in the end! :D 
Added by:  ahmed.abdrabo 
Date:  20130422 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  modified zeap from infoarena.ro 