1058:[ZJOI 2007]レポート統計

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
#include<map>
using namespace std;
inline int read(){
    int x=0,f=1;char ch;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int inf=1000000000+5;
const int N=500000+5;
int ms,head[N],tail[N];
int abs(int x){
    return max(x,-x);
}
multiset<int>s,mg;
map<int,int>mp;
void push(int x){
	mp[x]++;
	if(mp[x]==1)mg.insert(x);
}
void del(int x){
	mp[x]--;
	if(!mp[x])mg.erase(x);
}
int main(){
    int i,k,n,m;char opt[30];
    ms=inf;
    n=read();m=read();
    multiset<int>::iterator it;
    s.insert(-inf);s.insert(inf);
    for(i=1;i<=n;i++){
        k=read();head[i]=tail[i]=k;
        if(i!=1)push(abs(head[i]-head[i-1]));
        it=s.lower_bound(k);ms=min(ms,abs((*it)-k));
        ms=min(ms,abs((*--it)-k));
        s.insert(k);
    }
    while(m--){
        scanf("%s",opt);
        if(opt[0]=='I'){
            i=read();k=read();
            if(i!=n)del(abs(head[i+1]-tail[i]));
            push(abs(tail[i]-k));
            if(i!=n)push(abs(head[i+1]-k));
            it=s.lower_bound(k);ms=min(ms,abs((*it)-k));
            ms=min(ms,abs((*--it)-k));
            tail[i]=k;
            s.insert(k);
        }else if(opt[4]=='G')printf("%d
",*mg.begin());
        else printf("%d
",ms);
    }
    return 0;
}