#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<iostream>
#include<ctime>
#define ls t[x].son[0]
#define rs t[x].son[1]
#define maxn 500010
#define inf 2000021225
using namespace std;
inline int read() {
char ch = getchar(); int x = 0, f = 1;
while(ch < '0' || ch > '9') {
if(ch == '-') f = -1;
ch = getchar();
} while('0' <= ch && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
} return x * f;
}
inline void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
struct node{int val,son[2],fa;};
struct tree
{
node t[maxn<<2];int rt,cnt,mn;//bool in[maxn<<2];
//inline void pushup(int x){t[x].sz=t[rs].sz+t[ls].sz+1;}
inline void rotate(int x)
{
register int f=t[x].fa,gf=t[f].fa;
register int k=(t[f].son[1]==x),p=1^k;
t[gf].son[t[gf].son[1]==f]=x;t[x].fa=gf;
if(t[x].son[p]) t[t[x].son[p]].fa=f;t[f].son[k]=t[x].son[p];
t[x].son[p]=f;t[f].fa=x;//pushup(f);pushup(x);
}
inline void splay(int x,int goal)
{
if(!x) return;
while(t[x].fa!=goal)
{
int f=t[x].fa,gf=t[f].fa;
if(gf!=goal)
(t[gf].son[1]==f)^(t[f].son[1]==x)?rotate(x):rotate(f);
rotate(x);
}
if(!goal) rt=x;
}
int lower(int val)
{
register int x=rt,ans=-inf;
while(x){if(t[x].val==val) return val;if(t[x].val<val) ans=max(ans,t[x].val),x=rs;else x=ls;}
return ans;
}
int upper(int val)
{
register int x=rt,ans=inf;
while(x){if(t[x].val==val) return val;if(t[x].val>val) ans=min(ans,t[x].val),x=ls;else x=rs;}
return ans;
}
inline void insert(int val)
{
register int x=rt,lt=x;
if(!rt){x=++cnt;t[x].val=val;rt=x;return;}
if(val!=inf&&val!=-inf)
{
int lw=lower(val),up=upper(val);
mn=min(mn,(val-lw<0)?lw-val:val-lw),mn=min(mn,(up-val<0)?val-up:up-val);
}
while(x){lt=x;x=t[x].son[t[x].val<=val];}
x=lt;int k=(t[x].val<=val);t[x].son[k]=++cnt;lt=cnt;
t[lt].val=val;t[lt].fa=x;splay(lt,0);//in[lt]=1;
}
int find(int val)
{
int x=rt;
while(x)
{
if(t[x].val==val) return x;
x=t[x].son[t[x].val<val];
}
splay(x,0);
return x;
}
inline void del(int val)
{
register int x=find(val);splay(x,0);
if(!ls&&!rs){rt=0;return;}
if(!ls||!rs){int k=!ls;x=t[x].son[k];t[rt].son[k]=t[x].fa=0;rt=x;return;}
x=ls;while(rs) x=rs;splay(x,rt);//in[rt]=0;
rs=t[rt].son[1];t[t[rt].son[1]].fa=x;t[rt].son[0]=t[rt].son[1]=0;rt=x;t[x].fa=0;
}
int querymin(){int x=rt;while(ls) x=ls;splay(x,0);return t[x].val;}
//void dfs(int x){if(!x) return;dfs(ls);write(t[x].val);dfs(rs);}
//inline void cnm(){int x=rand()%cnt;if(in[x]) splay(x,0);}
}spaly,splay;// spaly -> original splay -> minus
vector<int> v[maxn];
int main()
{
register int n,i,q,x,p,val,bf;char ch[20];//srand(time(0));
//freopen("8.in","r",stdin);
//freopen("qaq.out","w",stdout);
n=read();q=read();
spaly.insert(-inf);spaly.insert(inf);spaly.mn=inf;
for(i=1;i<=n;++i)
{
x=read();
v[i].push_back(x);spaly.insert(x);
if(i>1) splay.insert(abs(v[i][0]-v[i-1][0]));
}
while(q--)
{
scanf("%s",ch);
//if(!rand()%100) splay.cnm(),spaly.cnm();
if(ch[0]=='I')
{
p=read();val=read();
bf=v[p][v[p].end()-v[p].begin()-1];
if(p<n) splay.del((v[p+1][0]-bf<0)?bf-v[p+1][0]:v[p+1][0]-bf),splay.insert((v[p+1][0]-val<0)?val-v[p+1][0]:v[p+1][0]-val);
splay.insert((val-bf<0)?bf-val:val-bf);spaly.insert(val);v[p].push_back(val);
}
else if(ch[4]=='S') write(spaly.mn),printf("
");
else write(splay.querymin()),printf("
");
}
return 0;
}
/**
3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP
*/以上代码来自bzoj1058
-luogu+O2通过
-luogu TLE 从T2个卡到T1个
-bzoj TLE
-bzoj+手动开O2 TLE
卡了一晚上常...
(玄学cnm优化也没用...
等你卡常技术够优秀了滚回来搞这玩意吧...