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
N , M ≤500000 对于所有的数据，序列内的整数不超过5*10^8。
题解
这是一道练习数据结构的好题
由于每次都是在原数列里加，其实难度就小了很多
对于原数列每个数，记录他最后一个加的数，假如没加就是自己
弄个可删堆维护第二个问题的答案
splay维护第三个问题的答案
对于第二个问题，设在第原数列第i个数后加数j，最后一个加的数为bck[i]
那么影响的其实就是bck[i]与i+1这两个数产生的结果，可删堆弄掉就好了
增加的影响是i,j和j,i+1
第三个问题，找一下前驱后继，维护全局答案即可
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
LL ans;
struct node
{int f,n,c,d,son[2];
}tr[1110000];int len,root;
void add(int d,int f)
{len++;tr[len].f=f;tr[len].c=tr[len].n=1;tr[len].d=d;tr[len].son[0]=tr[len].son[1]=0;if(d<tr[f].d)tr[f].son[0]=len;else tr[f].son[1]=len;
}
int update(int now)
{int lc=tr[now].son[0],rc=tr[now].son[1];tr[now].c=(tr[lc].c+tr[rc].c+tr[now].n);
}
void rotate(int x,int w)
{int f=tr[x].f,ff=tr[f].f;int R,r;R=f;r=tr[x].son[w];tr[R].son[1-w]=r;if(r!=0)tr[r].f=R;R=ff;r=x;if(tr[R].son[0]==f)tr[R].son[0]=r;else tr[R].son[1]=r;tr[r].f=R;R=x;r=f;tr[R].son[w]=r;tr[r].f=R;update(f);update(x);
}
void splay(int x,int rt)
{while(tr[x].f!=rt){int f=tr[x].f,ff=tr[f].f;if(ff==rt){if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);}else{if(tr[ff].son[0]==f && tr[f].son[0]==x){rotate(f,1);rotate(x,1);}else if(tr[ff].son[1]==f && tr[f].son[0]==x){rotate(x,1);rotate(x,0);}else if(tr[ff].son[1]==f && tr[f].son[1]==x){rotate(f,0);rotate(x,0);}else rotate(x,0),rotate(x,1);}}if(rt==0)root=x;
}
int findip(int d)
{int x=root;while(1){if(d<tr[x].d){if(tr[x].son[0]!=0)x=tr[x].son[0];else return x;}else if(d>tr[x].d){if(tr[x].son[1]!=0)x=tr[x].son[1];else return x;}else return x;}
}
void ins(int d)
{int x=findip(d);if(len==0){add(d,0);root=len;return ;}if(tr[x].d==d){tr[x].n++;update(x);return ;}else{add(d,x);update(len);update(x);}
}
int findqianqu(int d)
{int x=findip(d); if(d==tr[x].d)return tr[x].d;splay(x,0);if(tr[x].son[0]==0)return 1073741824;if(d<=tr[x].d){x=tr[x].son[0];while(tr[x].son[1]!=0) x=tr[x].son[1];}return tr[x].d;
}
int findhouji(int d)
{int x=findip(d); if(d==tr[x].d)return tr[x].d;splay(x,0);if(tr[x].son[1]==0)return 1073741824;if(tr[x].d<=d){x=tr[x].son[1];while(tr[x].son[0]!=0) x=tr[x].son[0];}return tr[x].d;
}
int n,m;
int fro[510000],bck[510000];//原数列第i个前面的/后面的 struct heap
{priority_queue<int,vector<int>,greater<int> > a,b;void push(int x){a.push(x);}void erase(int x){b.push(x);}void pop(){while(b.size() && b.top()==a.top())a.pop(),b.pop();a.pop();}int top(){while(b.size() && b.top()==a.top())a.pop(),b.pop();if(!a.size())return 0;return a.top();}
}h;
int a[510000];
int col[510000];
char ss[40];
int main()
{scanf("%d%d",&n,&m);len=0;ans=(1<<30);for(int i=1;i<=n;i++){scanf("%d",&col[i]);bck[i]=col[i];ins(col[i]);a[i]=col[i];}sort(a+1,a+1+n);for(int i=2;i<=n;i++)ans=min(ans,(LL)a[i]-a[i-1]);for(int i=1;i<n;i++)h.push(abs(col[i]-col[i+1]));while(m--){scanf("%s",ss+1);if(ss[1]=='I'){int u,v;scanf("%d%d",&u,&v);if(u!=n){h.erase(abs(col[u+1]-bck[u]));h.push(abs(col[u+1]-v));h.push(abs(v-bck[u]));bck[u]=v;}else{h.push(abs(v-bck[u]));bck[u]=v;}int p=findqianqu(v),q=findhouji(v);if(p!=1073741824)ans=min(ans,(LL)v-p);if(q!=1073741824)ans=min(ans,(LL)q-v);ins(v);}else if(ss[5]=='G')printf("%d\n",h.top());else printf("%lld\n",ans);}return 0;
}