代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
const int inf=1e9;

int n,m,in,last;
int MIN_SORT_GAP=inf;
vector<int> a[N];
priority_queue<int,vector<int>, greater<int> > exsit,del;
struct FHQTree{
    struct Node{int val,ls,rs,pri,siz;}t[N<<1];
    int cnt=0,root=0;
    int newNode(int val){
        t[++cnt].siz=1;t[cnt].ls=t[cnt].rs=0;
        t[cnt].pri=rand();t[cnt].val=val;
        return cnt;
    }
    void Up(int id){t[id].siz=t[t[id].ls].siz+t[t[id].rs].siz+1;}
    void Split(int id, int val, int &L, int &R){ // 排名分裂,L最终应含有k个元素
        if(!id){L=R=0;return;}
        if(t[id].val<=val){L=id;Split(t[id].rs,val,t[id].rs,R);}
        else{R=id;Split(t[id].ls,val,L,t[id].ls);}
        Up(id);
    }
    int Merge(int L, int R){
        if(!L&&!R) return L+R;
        if(t[L].pri>t[R].pri){t[L].rs=Merge(t[L].rs,R);Up(L);return L;}
        else{t[R].ls=Merge(L,t[R].ls);Up(R);return R;}
    }
    int Val(int id,int k){
        if(!k) return 0;
        if(k==t[t[id].ls].siz+1) return t[id].val;
        else if(k>t[t[id].ls].siz+1) return Val(t[id].rs,k-(t[t[id].ls].siz+1));
        else if(k<=t[t[id].ls].siz) return Val(t[id].ls,k);
    }
    void Insert(int val,bool flag=1){
        int L,R;Split(root,val,L,R);
        if(flag) MIN_SORT_GAP=min(MIN_SORT_GAP,min(val-Val(L,t[L].siz),Val(R,1)-val));
        root=Merge(Merge(L,newNode(val)),R);
    }
    void Out(int id){ // 中序遍历,打印结果
        if(!id) return;
        Out(t[id].ls);printf("%d ",t[id].val);Out(t[id].rs);
    }
}T;

int main(){
    freopen("P1110_5.in", "r", stdin);
    scanf("%d%d",&n,&m);
    T.Insert(0,0);T.Insert(inf,0);
    for(int i=1; i<=n; i++){
        scanf("%d", &in);cout<<i<<endl;
        a[i].push_back(in);
        if(i!=1) exsit.push(abs(in-last));last=in;
        T.Insert(in);
    }
    for(int i=1,rk,val; i<=m; i++){
        char opt[N];scanf("%s",opt);
        if(opt[0]=='I'){
            scanf("%d%d",&rk,&val);
            if(MIN_SORT_GAP) T.Insert(val);
            if(rk!=n){del.push(abs(a[rk+1].front()-a[rk].back()));exsit.push(abs(a[rk+1].front()-val));}
            exsit.push(abs(val-a[rk].back()));a[rk].push_back(val);
            while(exsit.top()==del.top()&&(!exsit.empty())&&(!del.empty())){exsit.pop(),del.pop();}
        }
        if(opt[4]=='G') printf("%d\n",exsit.top());
        if(opt[4]=='S') printf("%d\n",MIN_SORT_GAP);
    }
    return 0;
}

下载了#5测试点数据但是本地跑不动，读入第25198个元素会卡住（不清楚为什么每次都能精确的卡在第25198个元素）