Description
小Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。经过仔细观察，小Q发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作： INSERT i k 在原数列的第i个元素后面添加一个新元素k； 如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子） MIN_GAP 查询相邻两个元素的之间差值（绝对值）的最小值 MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值（绝对值） 例如一开始的序列为 5 3 1 执行操作INSERT 2 9将得到： 5 3 9 1 此时MIN_GAP为2，MIN_SORT_GAP为2。 再执行操作INSERT 2 6将得到： 5 3 9 6 1 注意这个时候原序列的第2个元素后面已经添加了一个9，此时添加的6应加在9的后面。这个时候MIN_GAP为2，MIN_SORT_GAP为1。于是小Q写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
Input
第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。第二行为N个整数，为初始序列。接下来的M行每行一个操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一种（无多余空格或者空行）。
Output
对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令，输出一行答案即可。
Sample Input
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
Sample Output
2
2
1
HINT
对于30%的数据，N ≤ 1000 , M ≤ 5000 对于100%的数据，N , M ≤500000 对于所有的数据，序列内的整数不超过5*108。
囧，又是splay，又被卡常数了，每次基本上都是对着数据调才调过的
我用两颗splay树，一个存所有的数（每次查前驱和后继更新答案），一个存所有的差值
当minsortgap为0时就不用再更新它了，还有，因为相邻的差值有一部分是不会被删除的，所以用min记录这些值中最小的值，大于等于min的差值就不用管它了（既不用删除，也不用插入）
搞了这么久终于过了（不过很慢，1300ms+）
const
maxn=;
type
node=record
son:array[..]of longint;
x,count,fa:longint;
end;
var
tree:array[..maxn*]of node;
a,b:array[..maxn]of longint;
n,m,mingap,minsortgap,min,tot,root1,root2:longint;
flag:boolean; procedure down(var x:longint;y:longint);
begin
if x>y then x:=y;
end; procedure rotate(x,w:longint;var root:longint);
var
y:longint;
begin
y:=tree[x].fa;
tree[y].son[w]:=tree[x].son[w xor ];
if tree[x].son[w xor ]<> then tree[tree[x].son[w xor ]].fa:=y;
tree[x].son[w xor ]:=y;
if root=y then root:=x
else
if tree[tree[y].fa].son[]=y then tree[tree[y].fa].son[]:=x
else tree[tree[y].fa].son[]:=x;
tree[x].fa:=tree[y].fa;
tree[y].fa:=x;
end; procedure splay(x,z:longint;var root:longint);
var
y:longint;
begin
while tree[x].fa<>z do
begin
y:=tree[x].fa;
if tree[y].fa=z then
if tree[y].son[]=x then rotate(x,,root)
else rotate(x,,root)
else
if tree[tree[y].fa].son[]=y then
if tree[y].son[]=x then
begin
rotate(y,,root);
rotate(x,,root);
end
else
begin
rotate(x,,root);
rotate(x,,root);
end
else
if tree[y].son[]=x then
begin
rotate(x,,root);
rotate(x,,root);
end
else
begin
rotate(y,,root);
rotate(x,,root);
end;
end;
end; function pre(now:longint):longint;
begin
now:=tree[now].son[];
while tree[now].son[]<> do
now:=tree[now].son[];
exit(now);
end; function succ(now:longint):longint;
begin
now:=tree[now].son[];
while tree[now].son[]<> do
now:=tree[now].son[];
exit(now);
end; procedure delete(x:longint);
var
now,l,r:longint;
begin
now:=root2;
while true do
begin
if now= then exit;
if tree[now].x=x then break;
if tree[now].x>x then now:=tree[now].son[]
else now:=tree[now].son[];
end;
splay(now,,root2);
if tree[root2].count> then dec(tree[root2].count)
else
begin
if (tree[root2].son[]=) or (tree[root2].son[]=) then
begin
if tree[root2].son[]<> then mingap:=tree[succ(root2)].x;
root2:=tree[root2].son[]+tree[root2].son[];
tree[root2].fa:=;
exit;
end;
l:=pre(root2);
r:=succ(root2);
splay(l,,root2);
splay(r,l,root2);
tree[r].son[]:=;
end;
end; procedure insert(x:longint;var root:longint);
var
now:longint;
begin
now:=root;
if root= then
begin
inc(tot);
root:=tot;
tree[tot].x:=x;
tree[tot].count:=;
if root=root2 then down(mingap,x);
exit;
end;
while true do
begin
if tree[now].x=x then
if root=root1 then
begin
minsortgap:=;
flag:=true;
exit;
end
else
begin
inc(tree[now].count);
exit;
end;
if tree[now].x>x then
if tree[now].son[]= then break
else now:=tree[now].son[]
else
if tree[now].son[]= then break
else now:=tree[now].son[];
end;
inc(tot);
tree[tot].x:=x;
tree[tot].count:=;
if x<tree[now].x then tree[now].son[]:=tot
else tree[now].son[]:=tot;
tree[tot].fa:=now;
splay(tot,,root);
if root=root1 then
begin
if tree[root].son[]<> then down(minsortgap,tree[root].x-tree[pre(root)].x);
if tree[root].son[]<> then down(minsortgap,tree[succ(root)].x-tree[root].x);
end
else down(mingap,x);
end; procedure init;
var
i:longint;
begin
read(n,m);
minsortgap:=maxlongint;
mingap:=maxlongint;
min:=maxlongint;
for i:= to n do
begin
read(a[i]);
b[i]:=a[i];
if flag=false then insert(a[i],root1);
if i> then insert(abs(a[i]-a[i-]),root2);
end;
readln;
end; procedure work;
var
i,x,y:longint;
c:char;
s:string;
begin
for i:= to m do
begin
read(c);
case c of
'I':begin
readln(c,c,c,c,c,x,y);
if x<n then
begin
if min>abs(b[x+]-y) then insert(abs(b[x+]-y),root2);
if min>abs(a[x]-b[x+]) then delete(abs(a[x]-b[x+]));
end;
down(min,abs(a[x]-y));
if flag=false then insert(y,root1);
a[x]:=y;
end;
'M':begin
readln(s);
if length(s)> then writeln(minsortgap)
else
begin
down(mingap,min);
writeln(mingap);
end;
end;
end;
end;
end; begin
init;
work;
end.