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写了一个程序，使 得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
这题有两种询问: 1.询问相邻两个数的差值的最小值 2.询问排序后相邻两个数的差值的最小值 我们只需要知道如何维护相邻两个数的差值最小值就可以。 由于插入时是按照初始顺序插入，所以我们不能破坏每个数在原来序列中的排名，一种解决办法是: 对于每个节点，只维护它的初始值，以及被插入的最后一个数，同时还需要维护每个节点所代表的字段（注意，不是子树）中的差值最小值（在每次插入时维护即可），以及以它为根的子树中的相邻两数差值的最小值，最后一个信息，可以通过维护它的前驱和后继来维护，一个数的前驱，就是它的左子树的最右边的数，一个数的后继，就是它的右子树的最左边的数，只需要维护两个值，lft,rgt,分别表示以它为根的子树的最左边的节点和最右边的节点，信息的更新函数如下：
int maintain(){ cnt=ch[0]->cnt+1+ch[1]->cnt;s=s1;lft=key;rgt=lst; if(ch[0]->key!=INF)lft=ch[0]->lft; if(ch[1]->key!=INF)rgt=ch[1]->rgt; if(ch[0]->rgt!=INF)s=min(s,abs(key-ch[0]->rgt)); if(ch[1]->lft!=INF)s=min(s,abs(lst-ch[1]->lft)); s=min(s,min(ch[0]->s,ch[1]->s)); }另外，在一个节点上加入一个数时，也要记得修改rgt的值，代码如下：
void add(int x){ s1=min(s1,abs(lst-x)); if(ch[1]->key==INF) rgt=x; lst=x; }给出代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #define maxn 500006 #define INF 1e9 using namespace std; int _read(){ int s=0,p;char ch=getchar(); while((ch!='-')&&(!(ch>='0'&&ch<='9')))ch=getchar(); if(ch=='-')p=-1,ch=getchar();else p=1; while(ch>='0'&&ch<='9')s=s*10+ch-48,ch=getchar(); return p*s; } struct node{ node* ch[2]; int key,cnt,lst,s,s1,lft,rgt; int maintain(){ cnt=ch[0]->cnt+1+ch[1]->cnt;s=s1;lft=key;rgt=lst; if(ch[0]->key!=INF)lft=ch[0]->lft; if(ch[1]->key!=INF)rgt=ch[1]->rgt; if(ch[0]->rgt!=INF)s=min(s,abs(key-ch[0]->rgt)); if(ch[1]->lft!=INF)s=min(s,abs(lst-ch[1]->lft)); s=min(s,min(ch[0]->s,ch[1]->s)); } void add(int x){ s1=min(s1,abs(lst-x)); if(ch[1]->key==INF) rgt=x; lst=x; } int cmp(int &k){ if(k<ch[0]->cnt+1)return 0; if(k==ch[0]->cnt+1)return -1; k-=ch[0]->cnt+1;return 1; } }nul; typedef node* pnode; pnode rt1,rt2,null=&nul; pnode newnode(int key){ pnode p=new node;p->key=key;p->ch[1]=p->ch[0]=null; p->lst=p->lft=p->rgt=key;p->cnt=1;p->s=p->s1=INF;return p; } void rot(pnode &p,int d){ pnode k=p->ch[d^1];p->ch[d^1]=k->ch[d];k->ch[d]=p; p->maintain();k->maintain();p=k; } void splay(pnode &p,int k){ int d1=p->cmp(k); if(d1!=-1){ int d2=p->ch[d1]->cmp(k); if(d2!=-1){ splay(p->ch[d1]->ch[d2],k); if(d2==d1)rot(p,d1^1); else rot(p->ch[d1],d2^1); } rot(p,d1^1); } } pnode build(int l,int r,int*arr){ if(l>r)return null; int mid=(l+r)>>1; pnode p=newnode(*(arr+mid)); p->ch[0]=build(l,mid-1,arr);p->ch[1]=build(mid+1,r,arr); p->maintain(); return p; } void insert(pnode &p,int k){ if(p==null)p=newnode(k);else{ int d=k>p->key; insert(p->ch[d],k); } p->maintain(); } void print_splay(pnode p){ if(p==null)return; print_splay(p->ch[0]); printf("%d ",p->key); print_splay(p->ch[1]); } int n,m,a[maxn],ans=INF,Min=INF,Max=-INF; int main(){ freopen("seq.in","r",stdin); freopen("seq.out","w",stdout); null->ch[0]=null->ch[1]=null;null->s=null->key=null->lst=null->lft=null->rgt=INF;null->cnt=0; rt1=rt2=null; n=_read();m=_read(); for(int i=1;i<=n;i++)a[i]=_read(); rt1=build(1,n,a); sort(a+1,a+1+n);rt2=build(1,n,a); for(int t=1;t<=m;t++){ char s[30],ch=getchar();int i=0; while(ch=='\n'||ch==' ')ch=getchar(); while(!(ch==EOF||ch=='\n'||ch==' '))s[i++]=ch,ch=getchar();s[i]='\0'; if(s[0]=='I'){ int x=_read(),y=_read(); splay(rt1,x);rt1->add(y);rt1->maintain(); insert(rt2,y); }else if(s[4]=='S')printf("%d\n",rt2->s); else printf("%d\n",rt1->s); // printf("Splay2=");print_splay(rt2);printf("\n"); } return 0; }