题目描述
Q的妈妈是一个出纳，经常需要做一些统计报表的工作。今天是妈妈的生日，小Q希望可以帮妈妈分担一些工作，作为她的生日礼物之一。
经过仔细观察，小Q发现统计一张报表实际上是维护一个非负整数数列，并且进行一些查询操作。
在最开始的时候，有一个长度为N的整数序列，并且有以下三种操作：
INSERT i k：在原数列的第i个元素后面添加一个新元素k；如果原数列的第i个元素已经添加了若干元素，则添加在这些元素的最后（见下面的例子）
MIN_GAP：查询相邻两个元素的之间差值（绝对值）的最小值
MIN_SORT_GAP：查询所有元素中最接近的两个元素的差值（绝对值）
例如一开始的序列为
5 3 1
执行操作INSERT 2 9将得到：
5 3 9 1
此时MIN_GAP为2，MIN_SORT_GAP为2。
再执行操作INSERT 2 6将得到：
5 3 9 6 1
注意这个时候原序列的第2个元素后面已经添加了一个9，此时添加的6应加在9的后面。这个时候MIN_GAP为2，MIN_SORT_GAP为1。
于是小Q写了一个程序，使得程序可以自动完成这些操作，但是他发现对于一些大的报表他的程序运行得很慢，你能帮助他改进程序么？
输入输出格式
输入格式： 第一行包含两个整数N，M，分别表示原数列的长度以及操作的次数。
第二行为N个整数，为初始序列。
接下来的M行每行一个操作，即“INSERT i k”，“MIN_GAP”，“MIN_SORT_GAP”中的一种（无多余空格或者空行）。
输出格式： 对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令，输出一行答案即可。
输入输出样例
输入样例#1： 3 5 5 3 1 INSERT 2 9 MIN_SORT_GAP INSERT 2 6 MIN_GAP MIN_SORT_GAP 输出样例#1： 2 2 1 说明
对于30%的数据，N ≤ 1000 , M ≤ 5000
对于100%的数据，N , M ≤500000
对于所有的数据，序列内的整数不超过5*108。
时限2s
set+map 洛谷的评测机有点慢，T了两个点，BZOJ还是把我放过去了
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<set> #include<map> #include<algorithm> #include<vector> using namespace std; #define MAXN 500005 #define INF 1000000007 int n,m; set<int>s,ss; map<int,int>mp; vector<int>g[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]); ss.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 ch[33]; while(m--){ scanf("%s",ch); if(ch[4]=='R'){ scanf("%d%d",&pos,&val);pos--; g[pos].push_back(val); if(ms){ set<int>::iterator it = ss.lower_bound(val); if(it!=ss.begin()){ if(it==ss.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- *ss.begin())); } ss.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(ch[4]=='G') printf("%d\n",mg); else printf("%d\n",ms); } return 0; }