原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ1058.html
题目传送门 - BZOJ1058
题解
考虑用两个 multiset 分别维护两个答案。
一个直接按照权值维护，另一个维护一下相邻位置的差。
比较容易想到如何维护的吧，不多讲，看代码吧。
代码
#include
using namespace std;
const int N=500005;
int read(){int x=0,f=1;char ch=getchar();while (!isdigit(ch)&&ch!='-')ch=getchar();if (ch=='-')f=-1,ch=getchar();while (isdigit(ch))x=(x<<1)+(x<<3)+ch-48,ch=getchar();return x*f;
}
int n,m;
vector v[N];
multiset S1,S2;
int ans1;
int add1(int x){S1.insert(x);multiset :: iterator p=S1.find(x);multiset :: iterator L=p,R=p;--L,++R;ans1=min(ans1,min(abs((*p)-(*L)),abs((*p)-(*R))));
}
int main(){n=read(),m=read();S1.clear();S2.clear();S1.insert(-2e9);S1.insert(ans1=2e9);for (int i=1;i<=n;i++){int x=read();v[i].clear();v[i].push_back(x);add1(x);if (i>1)S2.insert(abs(v[i][0]-v[i-1][0]));}v[n+1].clear();v[n+1].push_back(2e9);S2.insert(abs(v[n+1][0]-v[n][0]));while (m--){char ch[40];int a,b;scanf("%s",ch);if (ch[0]=='I'){a=read(),b=read();add1(b);int k=(int)v[a].size();S2.erase(S2.find(abs(v[a][k-1]-v[a+1][0])));S2.insert(abs(v[a][k-1]-b));v[a].push_back(b);S2.insert(abs(b-v[a+1][0]));}else if (ch[4]=='G'){printf("%d
",*S2.begin());}else if (ch[4]=='S'){printf("%d
",ans1);}}return 0;
}