记录编号	355701	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2007] 报表统计	最终得分	100
用户昵称	__stdcall	是否通过	通过
代码语言	C++	运行时间	2.087 s
提交时间	2016-11-26 18:31:56	内存使用	5.08 MiB

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int MAXN = 500010;
const int INF = 0x7fffffff;
typedef set<int>::iterator siter;
typedef map<int,int>::iterator miter;

namespace io {
	const int BUFSZ = 1e6;
	char buf[BUFSZ]; int idx, end;
	void init() { idx = BUFSZ; }
	char getch() {
		if( idx == BUFSZ ) {
			end = fread( buf, 1, BUFSZ, stdin ); idx = 0;
		}
		if( idx == end ) return EOF;
		return buf[idx++];
	}
	int getint() {
		int num = 0; char ch; bool nega = false;
		while( isspace(ch=getch()) );
		if( ch == '-' ) {
			nega = true; ch=getch();
		}
		do {
			num *= 10; num += ch-'0';
		}while( isdigit(ch=getch()) );
		if( nega ) num = -num;
		return num;
	}
	int getstr( char *str ) {
		char ch;
		while( isspace(ch=getch()) );
		int idx = 0;
		do {
			str[idx++] = ch;
		}while( !isspace(ch=getch()) && ch != EOF );
		return idx;
	}
}
using io::getint;
using io::getstr;

int n,m;

set<int> msg_s; // min_sort_gap_set
int msg = INF; // min_sort_gap
void update_msg( int num ) {
	if( !msg ) return;
	pair<siter,bool> p = msg_s.insert(num);
	if( !p.second ) { msg = 0; return; }
	if( p.first != msg_s.begin() ) {
		siter it = p.first; --it;
		msg = min( msg, *p.first - *it );
	}
	siter end = msg_s.end(); --end;
	if( p.first != end ) {
		siter it = p.first; ++it;
		msg = min( msg, *it - *p.first );
	}
}

priority_queue< int, vector<int>, greater<int> > mg_pq; // min_gap_pq
priority_queue< int, vector<int>, greater<int> > mg_del_pq; // 存储已被删除的元素
int solid_mg = INF;
void add_mg( int num, bool solid ) {
	if( num >= solid_mg ) return;
	mg_pq.push(num);
	if( solid ) solid_mg = num;
}
void del_mg( int num ) {
	if( num >= solid_mg ) return;
	mg_del_pq.push(num);
	while( !mg_del_pq.empty() && mg_pq.top() == mg_del_pq.top() ) {
		mg_pq.pop(); mg_del_pq.pop();
	}
}

int head[MAXN], tail[MAXN];
void insert_back( int num, int idx ) {
	update_msg(num);
	if( idx == n ) add_mg( abs( num - tail[idx] ), true );
	else {
		del_mg( abs( tail[idx] - head[idx+1] ) );
		add_mg( abs( num - tail[idx] ), true );
		add_mg( abs( num - head[idx+1] ), false );
	}
	tail[idx] = num;
}

int main() {
    freopen( "form.in", "r", stdin );
    freopen( "form.out", "w", stdout );
	io::init(); n = getint(); m = getint();
	for( int i = 1; i <= n; ++i ) {
		head[i] = tail[i] = getint();
		update_msg( head[i] );
		if( i > 1 ) add_mg( abs( head[i] - head[i-1] ), false );
	}
	for( int i = 0; i < m; ++i ) {
		char order[20]; getstr(order);
		if( order[0] == 'I' ) { // INSERT
			int a,b; a = getint(); b = getint();
			insert_back(b,a);
		}
		else if( order[4] == 'S' ) // MIN_SORT_GAP
			printf( "%d\n", msg == INF ? 0 : msg );
		else // MIN_GAP
			printf( "%d\n", mg_pq.top() );
	}
	return 0;
}