题目链接

一开始自己想的是multiset维护顺序结构，然后查找所有的值差最小时候找加入的当前点的前驱以及后继，然后查找相邻两个的就用线段树维护一个差最小值~，但是后来发现是全局的，直接再开一个multiset维护相邻段之差就行了，但是set的话要删除，也挺费时间的，不是所有点相邻都往set里边装，比如在某一个段加一个点的时候他前一个点的差值直接用一个ans来储存最小，然后输出的时候差的set里边最小值与ans比较一下就行。

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<time.h>

#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define inff 0x3f3f3f3f
#define lowbit(x) x&(-x)
#define PI 3.14159265358979323846
#define min4(a, b, c, d) min(min(a,b),min(c,d))
#define min3(x, y, z) min(min(x,y),min(y,z))
#define pii make_pair
#define pr pair<int,int>
#define li __int128
void print(li x) {if(x>9) print(x/10);putchar(x%10+48);}
const int dir[4][2] = {0, -1, -1, 0, 0, 1, 1, 0};
typedef long long ll;
typedef unsigned long long ull;
const ll inFF = 9223372036854775807;
using namespace std;
const int maxn=1e6+5;
int st[maxn],ed[maxn];
multiset<int> s,ss;
char str[20];
int main()
{
    int n,m,x,val;
    cin>>n>>m;
    int ans=inff,anss=inff;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        st[i]=ed[i]=x;
    }
    for(int i=1;i<=n;i++)
    {
        if(i<n) ss.insert(abs(st[i]-st[i+1]));
        auto it=s.lower_bound(st[i]);
        if(it!=s.end()) ans=min(ans,*it-st[i]);
        if(it!=s.begin()) it--,ans=min(ans,st[i]-*it);
        s.insert(st[i]);
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%s",str);
        if(strcmp(str,"INSERT")==0)
        {
            scanf("%d %d",&x,&val);
            auto it=s.lower_bound(val);
            if(it!=s.end()) ans=min(ans,*it-val);
            if(it!=s.begin()) it--,ans=min(ans,val-*it);
            s.insert(val);
            anss=min(anss,abs(ed[x]-val));
            if(x!=n)
            {
                it=ss.lower_bound(abs(st[x+1]-ed[x]));
                ss.erase(it);
                ss.insert(abs(st[x+1]-val));
            }
            ed[x]=val;
        }
        else if(strcmp(str,"MIN_SORT_GAP")==0) printf("%d\n",ans);
        else printf("%d\n",min(anss,*ss.begin()));
    }
    return 0;
}