给定一个数列 需要实现三种操作：
①在某个数后面加入一个数，如果曾经加入过则加在之前加的数之后
②查询所有相邻两个数的差的最小值
③查询全局差的最小值
用一个set和一个map维护相邻两数的差值
每次插入就删除原来的差值，再插入新的差值
因为全局差值只降不增
所以再开一个set存出现过的数，每次二分查找后更新差值再插入
因为BZOJ评测不分点所以卡过了
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<map> #define LL long long #define clr(x,i) memset(x,i,sizeof(x)) using namespace std; const int N=500005,INF=1e9+1024; inline void read(int &x) { x=0;int f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0',ch=getchar();} x*=f; } map<int,int> md; set<int> s0,sd; int n,m,be[N],en[N],msg=INF; inline void push(int x) { int l=*--s0.lower_bound(x),r=*s0.lower_bound(x); msg=min(msg,min(x-l,r-x)); s0.insert(x); } int main() { read(n);read(m); s0.insert(INF);s0.insert(-INF); for(int i=1,a;i<=n;i++) { read(a); be[i]=en[i]=a; push(a); } for(int i=2;i<=n;i++) { int t=abs(be[i]-be[i-1]); sd.insert(t);md[t]++; } set<int>::iterator it; char op[13]; while(m--) { scanf("%s",op); if(op[0]=='I'){ int p,x,mx; read(p);read(x); if(p!=n) { mx=abs(en[p]-be[p+1]); if(!--md[mx])sd.erase(mx); //md[mx]--; } mx=abs(x-en[p]);sd.insert(mx);md[mx]++; mx=abs(x-be[p+1]);sd.insert(mx);md[mx]++; en[p]=x; push(x); } else if(op[4]=='G'){ it=sd.begin(); printf("%d\n",*it); } else{ printf("%d\n",msg); } } return 0; } 开O2没用（逃）
