[bzoj1058]-[ZJOI2007]报表统计

题目（BZOJ）
题目（洛谷）
 
这题就只让你查个前驱后继而已......
所以为什么要去手写splay或其他的呢？
开两个multiset就可以了。
常数？在洛谷的氧气下不存在的

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=1000050;
const int inf=0x3f3f3f3f;
int n,m,a[N],L[N],R[N],msg=inf;
char ss[25];
multiset <int> num,delta;
inline void update(int v){
	multiset <int>::iterator i=num.lower_bound(v);
	int tmp=*i-v;
	tmp=min(tmp,v-*--i);msg=min(msg,tmp);
	num.insert(v);
}
inline void ins(int x,int v){
	delta.insert(abs(v-R[x]));
	if(x!=n){
		delta.erase(delta.find(abs(R[x]-L[x+1])));
		delta.insert(abs(v-L[x+1]));
	}
	R[x]=v;
}
int main(){
	read(n),read(m);
	num.insert(-inf),num.insert(inf);
	for(int i=1;i<=n;++i){read(a[i]);L[i]=R[i]=a[i];}
	for(int i=1;i<n;++i)delta.insert(abs(a[i+1]-a[i]));
	for(int i=1;i<=n;++i)update(a[i]);
	for(int i=1;i<=m;++i){
		scanf(
		if(ss[5]=='R'){
			int pos,val;read(pos),read(val);
			update(val);ins(pos,val);
		}
		else if(ss[5]=='G')printf(
		else printf(
	}
	return 0;
}