题解：数据结构的基本操作，用STL可以完美实现，就是比较慢……

#include <cstdio>  #include <map>  #include <set>  #include <vector>#include <algorithm>const int MAXN=500005;  const int INF=~0U>>1; using namespace std;  int n,m;  sets,tr;  map<int, int>mp;  vectorg[MAXN];  int a[MAXN], b[MAXN];  int main(){      scanf("%d%d",&n,&m);      int mg=INF,ms=INF,pos,val;      for(int i=0;i<n;i++){          scanf("%d",&a[i]);          tr.insert(a[i]);          b[i]=a[i];          if(i){              int k=abs(a[i]-a[i - 1]);              s.insert(k); mp[k]++;          }      }      sort(b,b+n);      for(int i=1;i<n;i++)ms=min(ms,b[i]-b[i-1]);      mg=*s.begin();      char op[33];      while(m--){          scanf("%s",op);          if(op[4]==‘R‘){              scanf("%d%d",&pos,&val); pos--;              g[pos].push_back(val);              if(ms){                set::iterator it=tr.lower_bound(val);                  if(it!=tr.begin()){                      if(it==tr.end()){                          it--;                          ms=min(ms,abs(val-*it));                      }                      else{                          int x=*it; it--;                          int y=*it;                          ms=min(ms,abs(x-val));                          ms=min(ms,abs(y-val));                      }                  }                  else ms=min(ms,abs(val-*tr.begin()));              }              tr.insert(val);              int x,y=INF;              if(g[pos].size()==1)x=a[pos];              else x=g[pos][g[pos].size()-2];              if(pos+1<n){                  y=a[pos+1];                  int k=abs(x-y); mp[k]--;                  if(mp[k]==0)s.erase(k);                  k=abs(x-val); s.insert(k);                  mp[k]++;                  k=abs(y-val); s.insert(k);                  mp[k]++; mg=*s.begin();              }              else{                  int k=abs(x-val);                  s.insert(k);                  mp[k]++; mg=*s.begin();              }          }          else if(op[4]==‘G‘) printf("%d\n", mg);          else printf("%d\n", ms);      }      return 0;  }