rt，lz打了两个平衡树维护，本地跑了个拍子1e3都过了，但是交洛谷的时候不开启O2会这样无O2

但是开起了O2会这样开O2

lz使用了随机化，所以明白可能是运气不好，于是多交了几次，变成了AC

然后不开O2，又开始鬼畜无O2

然后楼主加了一些鬼畜优化，变成了开O2完美AC

但是关掉O2又会鬼畜WA+TLE

lz十分疑惑，于是来求助万能的谷民，这O2是什么鬼..

贴一下代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
struct Treap{
    int size[N],cnt[N],val[N],ch[N][2],dat[N];
    int tot,rt,lmt;
    int New(int x){
        size[++tot]=1;
        cnt[tot]=1;
        val[tot]=x;
        dat[tot]=rand();
        return tot;
    }
    void push_up(int id){
        size[id]=size[ch[id][1]]+size[ch[id][0]]+cnt[id];
    }
    void rotate(int &id,int d){
        int tmp=ch[id][d^1];
        ch[id][d^1]=ch[tmp][d];
        ch[tmp][d]=id;
        id=tmp;
        push_up(ch[id][d]);
        push_up(id);
    }
    void ins(int &id,int v){
        if(!id){
            id=New(v);
            return;
        }
        if(val[id]==v){
            if(cnt[id]==1) lmt++;
            cnt[id]++;
        }else{
            int d=val[id]<v;
            ins(ch[id][d],v);
            if(dat[ch[id][d]]>dat[id]){
                rotate(id,d^1);
            }           
        }
        push_up(id);
        return;
    }
    void del(int &id,int v){
        if(!id) return;
        if(val[id]==v){
            if(cnt[id]>1){
                if(cnt[id]==2) lmt--;
                cnt[id]--;
                push_up(id);
                return;
            }
            if(ch[id][1]||ch[id][0]){
                if(!ch[id][1]||dat[ch[id][1]]<dat[ch[id][0]]){
                    rotate(id,1);del(ch[id][1],v);
                }else{
                    rotate(id,0);del(ch[id][0],v);
                }
                push_up(id);
            }else id=0;
            return;
        }
        int d=val[id]<v;
        del(ch[id][d],v);       
        push_up(id);
    }
    int getpre(int x){
        int id=rt,pre;
        while(id){
            if(val[id]<x){
                pre=val[id];
                id=ch[id][1];
            }else id=ch[id][0];
        }
        return pre;
    }
    int getnxt(int x){
        int id=rt,nxt;
        while(id){
            if(val[id]>x){
                nxt=val[id];
                id=ch[id][0];
            }else id=ch[id][1];
        }
        return nxt;
    }
    int getmin(){
        int id=rt;
        int res;
        while(id){          
            res=val[id];
            id=ch[id][0];
        }
        return res;
    }
}a,b;
int n,m;
int sg=0x7f7f7f7f;
vector<int> v[N];
signed main(){
    srand(time(NULL));
//  freopen("test.in","r",stdin);
//  freopen("tp.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        v[i].push_back(x);
        b.ins(b.rt,x);
    }
    for(int i=2;i<=n;i++){
        int t=abs(v[i][0]-v[i-1][0]);
        a.ins(a.rt,t);
    }
    for(int i=1;i<=n;i++){
        sg=min(sg,min(abs(v[i][0]-b.getpre(v[i][0])),abs(v[i][0]-b.getnxt(v[i][0]))));
    }
    if(b.lmt) sg=0;
    for(int i=1;i<=m;i++){
        string opt;
        cin>>opt;
        if(opt=="INSERT"){
            int l,r;
            cin>>l>>r;
            a.del(a.rt,abs(v[l][v[l].size()-1]-v[min(n,l+1)][0]));
            a.ins(a.rt,abs(r-v[l][v[l].size()-1]));
            a.ins(a.rt,abs(r-v[min(n,l+1)][0]));
            v[l].push_back(r);
            b.ins(b.rt,r);
            if(b.lmt) sg=0;
            sg=min(sg,min(abs(r-b.getpre(r)),abs(r-b.getnxt(r))));
        }else if(opt=="MIN_SORT_GAP") cout<<sg<<endl;
        else{
            cout<<a.getmin()<<endl;
        }
    }
return 0;
}