14pts 悬多关求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
mt19937 rnd(time(nullptr));

const int inf = 0x7f7f7f7f;
const int N = 1e6 + 10;
const int M = 30;
int n,m;
vector<int> a[N];
string op;
int mnn = inf;
typedef struct chain{
    int val,dto[M + 10];
    struct chain* nxt[M + 10];
}* cp;
cp head,upd[M + 10];
int lv,tot[M + 10];
priority_queue<int,vector<int>,greater<int>> p1,p2;

void build(){
    lv = 1;
    head = new(chain);
    head->val = -inf;
    for(int i = M;i >= 1;-- i){
        head->nxt[i] = nullptr;
        upd[i] = head;
    }
    return;
}

int rndlvl(){
    int x = 1;
    for(;(rnd() & 1) && x < M;++ x);
    return x;
}

int rnk(int x){
    cp p = head;
    tot[lv + 1] = 0;
    for(int i = lv;i >= 1;-- i){
        tot[i] = tot[i + 1];
        while(p->nxt[i] && p->nxt[i]->val < x)
            tot[i] += p->dto[i],p = p->nxt[i];
        upd[i] = p;
    }
    return tot[1] + 1;
}

void insert(int x){
    cp p = new(chain);
    p->val = x;
    rnk(x);
    int lay = rndlvl();
    lv = max(lay,lv);
    for(int i = 1;i <= lay;++ i){
        p->nxt[i] = upd[i]->nxt[i];
        p->dto[i] = upd[i]->dto[i] - (tot[1] - tot[i]);
        upd[i]->nxt[i] = p;
        upd[i]->dto[i] = tot[1] - tot[i] + 1;
    }
    for(int i = lay + 1;i <= lv;++ i) ++ upd[i]->dto[i];
    return;
}

int getpre(int x){
    cp p = head;
    for(int i = lv;i >= 1;-- i)
        while(p->nxt[i] && p->nxt[i]->val < x)
            p = p->nxt[i];
    if(p->val != inf) return p->val;
    return -inf;
}

int getnxt(int x){
    cp p = head;
    for(int i = lv;i >= 1;-- i)
        while(p->nxt[i] && p->nxt[i]->val <= x)
            p = p->nxt[i];
    if(p->nxt[1]) return p->nxt[1]->val;
    return inf;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    build();
    cin >> n >> m;
    for(int i = 1;i <= n;++ i){
        int x;
        cin >> x;
        a[i].emplace_back(x);
        insert(x);
        if(i != 1) p1.push(abs(x - a[i - 1][0]));
        mnn = min(mnn,getnxt(x) - x);
        mnn = min(mnn,x - getpre(x));
    }
    while(m --){
        cin >> op;
        if(op == "INSERT"){
            int x,y;
            cin >> x >> y;
            insert(y);
            mnn = min(mnn,getnxt(y) - y);
            mnn = min(mnn,y - getpre(y));
            if(x < n) p2.push(abs(a[x][a[x].size() - 1] - a[x + 1][0]));
            p1.push(abs(y - a[x][a[x].size() - 1]));
            if(x < n) p1.push(abs(y - a[x + 1][0]));
            a[x].emplace_back(y);
        }else if(op == "MIN_GAP"){
        	while(p2.top() == p1.top())
        		p1.pop(),p2.pop();
      		cout << p1.top() << '\n';
        }else cout << mnn << '\n';
    }
    return 0;
}