[文章目录]
Description
三种操作： 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。N , M ≤500000
发现对两个询问，1.把所有数存一下，加数的时候扔到set里更新答案。2.维护一个set，每次删除一个值，加两个值。
#include <set>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans=1<<30,aft[501000],fro[501000];
char st[30];
set<int>s1;
set<int>::iterator it;
multiset<int>s2;
multiset<int>::iterator it2;
inline int Abs(int x){return x>0?x:-x;}
void Insert()
{
int x,y; scanf("%d%d",&x,&y);
if(x<n)
{
it2=s2.lower_bound(Abs(aft[x]-fro[x+1]));
s2.erase(it2);
s2.insert(Abs(y-fro[x+1]));
}
s2.insert(Abs(y-aft[x])); aft[x]=y;
it=s1.lower_bound(y);
if(it!=s1.end()) ans=min(ans,Abs(y-*it));
if(it!=s1.begin()) it--,ans=min(ans,Abs(y-*it));
s1.insert(y);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",fro+i);
if(s1.size())
{
it=s1.lower_bound(fro[i]);
if(it!=s1.end()) ans=min(ans,Abs(fro[i]-*it));
if(it!=s1.begin()) it--,ans=min(ans,Abs(fro[i]-*it));
}
aft[i]=fro[i];
s1.insert(fro[i]);
if(i!=1) s2.insert(Abs(fro[i]-fro[i-1]));
}
while(m--)
{
scanf("%s",st);
switch(st[4])
{
case 'R':Insert(); break;
case 'S':printf("%d\n",ans); break;
case 'G':printf("%d\n",*s2.begin()); break;
}
}
return 0;
}