题目链接
比较简单的一道平衡树题。
第三个操作可以直接用map完成(加进去一个数只会让答案变小，于是与它的前面后面一个数做差更新答案即可)，只考虑前两个操作。
·维护区间内的最大最小值，以及区间相邻两数最小差值。
·对于insert x k ,相当于在x+1前插入k,再用一个树状数组维护原数组中的每个数在现在的数组中是第几个，这个操作相当于对 x+1 ~ n 的排名全部加了1。
复杂度O(nlogn) ,常数略大...
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<cassert>
#define P puts("lala")
#define cp cerr<<"lala"<<endl
#define ln putchar('\n')
#define sp putchar(' ')
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef pair<int,int> pii;
inline void read(int &re)
{
char ch=getchar();int g=1;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
re=0;
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();
re*=g;
}
typedef long long ll;
inline void read(ll &re)
{
char ch=getchar();ll g=1;
while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}
re=0;
while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48ll,ch=getchar();
re*=g;
} const int N=500050;
const int inf=0x3f3f3f3f;
map<int,int>mp;
map<int,int>::iterator it,it1; int dv[N],n,m;
inline void add(int x,int k)
{
for(;x<=n;x+=(x&-x)) dv[x]+=k;
}
inline int ask(int x)
{
int sum=0;
for(;x>0;x-=(x&-x)) sum+=dv[x];
return sum;
} int key[N<<1],mind[N<<1],ch[N<<1][2],fa[N<<1],pre[N<<1],nex[N<<1];
int a[N],sz,root,siz[N<<1]; inline void up(int o)
{
mind[o]=min(mind[ch[o][0]],mind[ch[o][1]]);
pre[o]=key[o];nex[o]=key[o];
siz[o]=1;
if(ch[o][0])
{
mind[o]=min(mind[o],abs(key[o]-nex[ch[o][0]]));
pre[o]=pre[ch[o][0]];
siz[o]+=siz[ch[o][0]];
}
if(ch[o][1])
{
mind[o]=min(mind[o],abs(key[o]-pre[ch[o][1]]));
nex[o]=nex[ch[o][1]];
siz[o]+=siz[ch[o][1]];
}
} void build(int &o,int l,int r)
{
if(l>r) return ;
o=++sz;
int mid=l+r>>1;
key[o]=a[mid];
siz[o]=1;
pre[o]=a[mid];nex[o]=a[mid];
mind[o]=inf;
if(l==r) return ;
build(ch[o][0],l,mid-1);build(ch[o][1],mid+1,r);
fa[ch[o][0]]=o;fa[ch[o][1]]=o;
up(o);
} inline bool ge(int x){return ch[fa[x]][1]==x;}
inline void rotate(int x)
{
int f=fa[x],g=fa[f],wh=ge(x);
ch[f][wh]=ch[x][wh^1];fa[ch[f][wh]]=f;
ch[x][wh^1]=f;fa[f]=x;
fa[x]=g;
if(g) ch[g][ch[g][1]==f]=x;
up(f);up(x);
}
void splay(int x)
{
for(int f;f=fa[x];rotate(x)) if(fa[f]) rotate(ge(x)==ge(f)?f:x);
root=x;
}
int find(int k)
{
//assert(k<=siz[root]);
//assert(k>=1);
int x=root;
while(1)
{
if(k<=siz[ch[x][0]]) x=ch[x][0];
else
{
k-=siz[ch[x][0]];
if(k<=1) return x;
k--;
x=ch[x][1];
}
}
} void inspre(int k)
{
int x=ch[root][0];
while(ch[x][1]) x=ch[x][1];
ch[x][1]=++sz;siz[sz]=1;
pre[sz]=k;key[sz]=k;nex[sz]=k;
fa[sz]=x;mind[sz]=inf;
up(x);
splay(sz);
} char in[50];
int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);freopen("1.out","w",stdout);
#endif
int i,j,opt,T;
mind[0]=inf;
read(n);read(m);
for(i=1;i<=n;++i) add(i,1);
for(i=1;i<=n;++i) read(a[i]),mp[a[i]]++;
build(root,1,n);
int minn=inf;
for(it=mp.begin();it!=mp.end();++it)
{
it1=it;
it1++;
if(it1!=mp.end()) minn=min(minn,abs( (it->fi)-(it1->fi) ));
if((it->second)>1) minn=0;
}
siz[0]=0;
for(int cas=1;cas<=m;++cas)
{
scanf("%s",in);
if(in[0]=='I')
{
int x,k;read(x);read(k);
//cerr<<cas<<endl;
if(x+1>n)
{
int rt=find(siz[root]);
splay(rt);
root=++sz;
ch[sz][0]=rt;
fa[rt]=sz;
key[sz]=k;mind[sz]=inf;
up(sz);
}
else
{
int rt=find(ask(x+1));
splay(rt);
//cout<<siz[root]<<endl;
inspre(k);
}
mp[k]++;
it=mp.find(k);
if((it->se)>1) minn=0;
else
{
it1=it;
if(it1!=mp.begin())
{
it1--;
minn=min(minn,abs((it1->fi)-k));
}
it++;
if(it!=mp.end()) minn=min(minn,abs((it->fi)-k));
}
add(x+1,1);
}
else if(in[4]=='G') printf("%d\n",mind[root]);
else if(in[4]=='S') printf("%d\n",minn);
}
return 0;
}
/* */
