题解：数据结构的基本操作，用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;

}