TREAP - Yet another range difference query!

no tags 

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

 

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: 2018-08-31 11:16:01

Why my solution is black, and shows 0K, Result: 0.

fz0718: 2017-07-22 23:10:28

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

mahmud2690: 2016-05-25 13:30:54

Why my solution is black, and shows 0K, Result: 0.

timonknigge: 2015-08-31 15:20:40

It might be worth pointing out that for the N query, we also require that x =/= y.

bicsi: 2015-07-02 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:2013-04-22
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:modified zeap from infoarena.ro