考察点：STL 的熟练运用。
记：\(l_i\) 表示序列中不超过 \(a_i\) 的最大数，\(r_i\) 表示序列中超过 \(a_i\) 的最小数。
开一个 vector insert[N] 存储 \(a_i\) 后面插入的所有数字。
首先，我们使用一个 multiset s1 来存储相邻元素的差的绝对值，然后再开一个 multiset s2 来存储当前出现的所有元素，然后维护一个变量 \(ans\)，表示操作三的答案。
此时，我们就可以直接完成操作二三了（操作二访问 *s1.begin()，操作三直接输出 \(ans\)）。
下面我们来讲一下这些东西的预处理。
首先，我们将所有的 \(a_i\) 扔进 s2 中。根据 \(l_i\) 和 \(r_i\) 的定义，可以直接使用 lower/upper_bound() 函数找出，然后更新 \(ans=\min(ans,\min(|r_i-a_i|,|l_i-a_i))\)，并将 \(|a_i-a_{i-1}|\) 插入到 s1 当中。
注意：我们在更新 \(ans\) 时，由于我们已经提前将所有 \(a_i\) 放入 s2 中，所以查找到的结果是 \(a_i\) 本身，此时需要将指针再前/后移一位，并判断是否越界。
预处理的代码如下：
inline void init(){
for(int i=1;i<=n;++i){
a[i]=read();
if(i!=1)s1.insert(abs(a[i]-a[i-1]));
s2.insert(a[i]);
}
for(int i=1;i<=n;++i){
auto x=s2.lower_bound(a[i]);
if(x!=s2.end())ans=min(ans,abs(a[i]-*(++x)));
auto y=s2.upper_bound(a[i]);
if(y!=s2.begin()&&--y!=s2.begin())ans=min(ans,abs(a[i]-*(--y)));
}
}
接下来，我们只需要考虑操作一会带来的影响。
我们记 \(pre\) 表示当前位置的前一个元素。显然，如果 insert[x] 为空，那么 \(pre=a_x\)，否则为 insert[x].back()（此时还没有插入 \(y\)）。
我们考虑当前位置的加入会影响到哪些位置：类似链表插入，显然这次插入会断掉 \(pre\) 和 \(a_{x+1}\) 之间的联系（如果 \(x=n\)，则忽略，否则 erase 时会 \(\color{purple}\text{RE}\)），并且使 \(pre\) 和 \(y\)、以及 \(y\) 和 \(a_{x+1}\) 成为邻居（同样 \(x=n\) 时不考虑）。然后使用 erase/insert 函数即可，注意删除单一元素时要用 find()。
这样 s1 就处理完了。对于 s2，我们还是先 lower/upper_bound() 一下，找到最接近元素（先查找再插入，不用移动），更新答案然后将 \(y\) 同时扔到 s2 和 insert[x] 里即可。
复杂度应该是单 \(\log\) 的，但是常数大，所以开了 O2 才能过（不开 \(70\)）。话说有没有人帮我卡卡常啊
最后是完整代码（操作一使用函数封装了下，比较整洁，但是调用函数会变慢）：
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
const int N=5e5+5;
using namespace std;
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline int read(){
int x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz-1;++i) pt(s[i]);
printf("\n");
}
int n,m,a[N],ans=0x3f3f3f3f;
vector<int>insert[N];
multiset<int>s1,s2;
string opt;
inline void solve(int x,int y){
x=read(),y=read();
int pre=insert[x].size()?insert[x].back():a[x];
insert[x].emplace_back(y);
if(x!=n)s1.erase(s1.find(abs(pre-a[x+1])));
s1.insert(abs(y-pre));
if(x!=n)s1.insert(abs(y-a[x+1]));
auto it=s2.lower_bound(y);
if(it!=s2.end())ans=min(ans,abs(y-*it));
auto it2=s2.upper_bound(y);
if(it2!=s2.begin())ans=min(ans,abs(y-*(--it2)));
s2.insert(y);
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i){
a[i]=read();
if(i!=1)s1.insert(abs(a[i]-a[i-1]));
s2.insert(a[i]);
}
for(int i=1;i<=n;++i){
auto x=s2.lower_bound(a[i]);
if(x!=s2.end())ans=min(ans,abs(a[i]-*(++x)));
auto y=s2.upper_bound(a[i]);
if(y!=s2.begin()&&--y!=s2.begin())ans=min(ans,abs(a[i]-*(--y)));
}
for(int x,y;m;--m){
cin>>opt;
if(opt=="INSERT")solve(x,y);
else if(opt=="MIN_GAP")println(*s1.begin());
else println(ans);
}
return 0;
}