【BZOJ 1058】【ZJOI 2007】レポート統計stlテンプレート

#include <set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 501000
#define inf 0x3f3f3f3f
using namespace std;

int n,m;
int src[N],last[N];
multiset<int>sorted,listed;
int sortmin=inf;
char opt[20];
int main()
{
	int i,j,k;
	int x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&src[i]);
		last[i]=src[i];
		sorted.insert(src[i]);
	}
	for(i=2;i<=n;i++)listed.insert(abs(src[i]-src[i-1]));
	multiset<int>::iterator l;
	for(multiset<int>::iterator it=sorted.begin();it!=sorted.end();++it)
	{
		if(it!=sorted.begin())sortmin=min(sortmin,abs(*it-*l));
		l=it;
	}
	while(m--)
	{
		scanf("%s",opt);
		if(opt[0]=='I')
		{
			scanf("%d%d",&x,&y);
			multiset<int>::iterator it=sorted.insert(y);
			it--,sortmin=min(sortmin,abs(y-*it)),it++;
			it++,sortmin=min(sortmin,abs(y-*it)),it--;

			it=listed.find(abs(last[x]-src[x+1]));
			listed.erase(it);
			listed.insert(abs(y-last[x]));
			listed.insert(abs(src[x+1]-y));
			last[x]=y;
		}
		else if(opt[4]=='S')printf("%d
",sortmin);
		else printf("%d
",*listed.begin());
	}
}