求卡常

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline string read(){
    string str="";
    char ch=getchar();
    while(ch==' ' || ch=='\n' || ch=='\r') ch=getchar();
    while(ch!=' ' && ch!='\n' && ch!='\r') str+=ch,ch=getchar();
    return str;
}
inline int read1(){
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
const int N=5e5+5;
int n,m,w;
int a[N],b[N];
int root,tot,ans2=LLONG_MAX;
struct node{
    int ls,rs,sz,sum,w;
}tree[N*5];
multiset<int> st;
void upd(int rt){
    if(rt) tree[rt].sz=tree[tree[rt].ls].sz+tree[tree[rt].rs].sz+1;
}
void split(int rt,int v,int &x,int &y){
    if(!rt) return x=y=0,void();
    if(tree[rt].sum>v) y=rt,split(tree[rt].ls,v,x,tree[rt].ls);
    else x=rt,split(tree[rt].rs,v,tree[rt].rs,y);
    upd(rt);
}
void merge(int x,int y,int &rt){
    if(!x||!y) rt=x+y;
    else if(tree[x].w>=tree[y].w) rt=x,merge(tree[x].rs,y,tree[rt].rs);
    else rt=y,merge(x,tree[y].ls,tree[rt].ls);
    upd(rt);
}
void ins(int &rt,int x){
    int rt1=0,rt2=0,k=++tot;
    tree[tot]={0,0,1,x,rand()};
    split(rt,x,rt1,rt2);
    merge(rt1,k,rt1);
    merge(rt1,rt2,rt);
}
void del(int &rt,int x){
    int t1=0,t2=0,t3=0,t4=0,t5=0;
    split(rt,x,t1,t2),split(t1,x-1,t3,t4);
    merge(tree[t4].ls,tree[t4].rs,t4);
    merge(t3,t4,t5),merge(t5,t2,rt);
}
int kth(int rt,int x){
    int rt1=rt;
    while(rt1){
        if(tree[tree[rt1].ls].sz==x-1) return tree[rt1].sum;
        else if(tree[tree[rt1].ls].sz>=x) rt1=tree[rt1].ls;
        else x-=tree[tree[rt1].ls].sz+1,rt1=tree[rt1].rs;
    }
    return INT_MAX*3;
}
int pre(int rt,int x){
    int rt1=0,rt2=0,res=0;
    split(rt,x,rt1,rt2);
    res=kth(rt1,tree[rt1].sz);
    merge(rt1,rt2,rt);
    return res;
}
int aft(int rt,int x){
    int rt1=0,rt2=0,res=0;
    split(rt,x-1,rt1,rt2);
    res=kth(rt2,1);
    merge(rt1,rt2,rt);
    return res;
}
signed main(){
    srand(time(0));
    n=read1(),m=read1();
    for(int i=1;i<=n;i++) a[i]=read1(),ins(root,a[i]);
    for(int i=1;i<=n;i++){
        if(i!=1) st.insert(abs(a[i]-a[i-1]));
        del(root,a[i]);
        int t1=pre(root,a[i]),t2=aft(root,a[i]);
        ans2=min(ans2,min(abs(a[i]-t1),abs(t2-a[i])));
        ins(root,a[i]);
        b[i]=a[i];
    }
    while(m--){
        string str;
        str=read();
        if(str=="INSERT"){
            int x,y;
            x=read1(),y=read1();
            st.erase(st.find(abs(a[x+1]-b[x])));
            st.insert(abs(y-b[x]));st.insert(abs(a[x+1]-y));
            int t1=pre(root,y),t2=aft(root,y);
            // cout<<t1<<" "<<t2<<endl;
            ans2=min(ans2,min(abs(y-t1),abs(t2-y)));
            b[x]=y;ins(root,y);
        }
        else if(str=="MIN_GAP") printf("%lld\n",*st.begin());
        else printf("%lld\n",ans2);
    }
    return 0;
}