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。

---

题解Here!

 

恶心到极致的卡常题。。。

维护两个$Treap$即可。 

为什么不用$Splay$？

因为

这个题目$BZOJ$用事实告诉我们：

$Splay$的常数是$Treap$的许多倍。。。

第一颗$Treap$：维护每个点，每次新加入一个点时，找到前驱后继，维护第$3$个操作的答案。 

第二颗$Treap$：每次加入点时，维护相邻两个点之差的绝对值。

然后就没了。

但是这题疯狂卡常。。。

借鉴了网上的几个优化：

1. 对于第$2$个操作，我们注意到，加入一个点位置是$pos$时，$pos$与$pos-1$的差值不会消失，所以可以用一个$ans$来维护$pos$与前驱的之间的值。
2. 而$pos$与$pos+1$之间可能加入数字，所以用$Treap$维护。不过，若差值小于$ans$，就不用再加入$Treap$中了。
3. 还有，对于第$3$个操作，在统计是只要发现有两个数字相同，就做个标记，到后面询问时直接输出$0$即可。

以上所说的差值都要加绝对值。

然后就可以跑了。。。

附代码：

#include
      
       #include
       
        #include
        
         #define MAXN 500010#define MAX 999999999using namespace std;int n,m,minn=MAX;int head[MAXN],last[MAXN];bool flag;struct node{	node* son[2];	int w,v,s,flag;	node(){		son[0]=son[1]=NULL;		w=rand();		v=0;		s=flag=1;	}};node* one;node* two;inline int read(){	int date=0,w=1;char c=0;	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}	return date*w;}inline void write(int x){	if(x<0){putchar('-');x=-x;}	if(x>9)write(x/10);	putchar(x%10+'0');}inline long long abs(const long long x){return x>0?x:-x;}inline long long min(const long long x,const long long y){return x
         
          s=u->flag;	if(u->son[0]!=NULL)u->s+=u->son[0]->s;	if(u->son[1]!=NULL)u->s+=u->son[1]->s;}void turn(node* &u,int f){	node* t=u->son[f^1];	u->son[f^1]=t->son[f];	t->son[f]=u;	maintain(u);	maintain(t);	u=t;}void insert(node* &u,int x){	if(u==NULL){		u=new node;		u->v=x;		return;	}	else if(u->v==x){		u->flag++;		maintain(u);		if(flag)minn=-1;		return;	}	int y=u->v
          
           son[y],x);	if(u->son[y]->w>u->w)turn(u,y^1);	else maintain(u);}void remove(node* &u,int x){	if(u==NULL)return;	if(u->v==x){		if(u->flag>1)u->flag--;		else{			if(u->son[0]==NULL&&u->son[1]==NULL)u=NULL;			else if(u->son[0]!=NULL&&u->son[1]!=NULL){				if(u->son[0]->w>u->son[1]->w){					turn(u,1);					remove(u->son[1],x);				}				else{					turn(u,0);					remove(u->son[0],x);				}			}			else{				if(u->son[0]==NULL)u=u->son[1];				else u=u->son[0];			}		}		if(u!=NULL)maintain(u);	}	else{		if(u->v>x)remove(u->son[0],x);		else if(u->v
           
            son[1],x); if(u!=NULL)maintain(u); }}int kth(node* u,int k){ if(k<0||k>u->s||u==NULL)return 0; int lsons=0; if(u->son[0]!=NULL)lsons=u->son[0]->s; if(k>=lsons+1&&k<=lsons+u->flag)return u->v; if(k<=lsons)return kth(u->son[0],k); else return kth(u->son[1],k-lsons-u->flag);}void front(node* u,int k,int &ans){ if(u==NULL)return; if(u->v
            
             v>ans)ans=u->v; if(u->son[1]!=NULL)front(u->son[1],k,ans); } else if(u->v>=k) if(u->son[0]!=NULL)front(u->son[0],k,ans);}void next(node* u,int k,int &ans){ if(u==NULL)return; if(u->v>k){ if(u->v
             
              v; if(u->son[0]!=NULL)next(u->son[0],k,ans); } else if(u->v<=k) if(u->son[1]!=NULL)next(u->son[1],k,ans);}void update(int v){ int front_v=-MAX,next_v=MAX; front(one,v,front_v);next(one,v,next_v); minn=min(minn,min(abs(front_v-v),abs(next_v-v)));}void work(){ char ch[15]; int x,y,ans=MAX; while(m--){ scanf("%s",ch); if(ch[0]=='I'){ x=read();y=read(); flag=true; insert(one,y); if(minn!=-1)update(y); flag=false; ans=min(ans,abs(last[x]-y)); if(x!=n){ if(abs(head[x+1]-y)