_皎月半洒花 的博客

P1110 [ZJOI2007]报表统计

posted on 2018-05-10 21:32:07 | under 平时做题+数据结构 |

维护相邻最小差值：

$Code$ :

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 500001
#define Inf 2147483600
#define ll long long

using namespace std;
struct tree{
ll v,sub,son[2],f,cnt;
}s[MAXN<<1],S[MAXN<<1];
ll minn=Inf,root,wz,num[MAXN],base[MAXN],i,now,res,pre,suffix,fa;
ll _res,_wz,_root,_now,_fa,_rank,_old_root;

long long num=0;
char ch=getchar();
while(!isdigit(ch)){
ch=getchar();
}
while(isdigit(ch)){
num=(num<<1)+(num<<3)+ch-'0';
ch=getchar();
}
return num;
}
/*___________________________________________________________*/
inline ll my_abs(ll x){
return x>0?x:-x;
}
inline bool which(ll x){
return x==s[s[x].f].son[1];
}
inline void update(ll x){
if(x){
s[x].sub=s[x].cnt;
if(s[x].son[0])s[x].sub+=s[s[x].son[0]].sub;
if(s[x].son[1])s[x].sub+=s[s[x].son[1]].sub;
}
}
inline void rotate(ll x){
ll fnow=s[x].f,ffnow=s[fnow].f;
bool w=which(x);
s[fnow].son[w]=s[x].son[w^1];
s[s[fnow].son[w]].f=fnow;
s[fnow].f=x;
s[x].f=ffnow;
s[x].son[w^1]=fnow;
if(ffnow){
s[ffnow].son[s[ffnow].son[1]==fnow]=x;
}
update(fnow);
}
inline void splay(ll x,ll goal){
for(ll qwq;(qwq=s[x].f)!=goal;rotate(x)){
if(s[qwq].f!=goal){
rotate(which(x)==which(qwq)?qwq:x);
}
}
if(goal==0){
root=x;
}
}
inline void insert(ll x){
if(!root){
wz++;
s[wz].son[0]=s[wz].son[1]=s[wz].f=0;
root=wz;
s[wz].sub=s[wz].cnt++;
s[wz].v=x;
return ;
}
now=root,fa=0;
while(1){
if(x==s[now].v){
s[now].cnt++;
update(now);
update(fa);
splay(now,0);
break;
}
fa=now;
now=s[now].son[s[now].v<x];
if(!now){
wz++;
s[wz].son[0]=s[wz].son[1]=0;
s[wz].f=fa;
s[wz].sub=s[wz].cnt++;
s[fa].son[s[fa].v<x]=wz;
s[wz].v=x;
update(fa);
splay(wz,0);
break;
}
}
}
inline ll find_pre(){
res=s[s[root].son[0]].v,now=s[root].son[0];
if(s[root].cnt>1)
return s[root].v;
while(s[now].son[1]){
res=s[s[now].son[1]].v;
now=s[now].son[1];
}
return res;
}
inline ll find_suffix(){
res=s[s[root].son[1]].v,now=s[root].son[1];
if(s[root].cnt>1)
return s[root].v;
while(s[now].son[0]){
res=s[s[now].son[0]].v;
now=s[now].son[0];
}
return res;
}
inline void init_insert(ll now){
insert(now);
suffix=find_suffix();
pre=find_pre();
if(suffix!=Inf){
minn=min(minn,my_abs(suffix-now));
}
if(pre!=-Inf){
minn=min(minn,my_abs(pre-now));
}
}

/*___________________________________________________________*/

inline bool S_which(ll x){
return x==S[S[x].f].son[1];
}
inline void S_clear(ll x){
S[x].cnt=S[x].son[1]=S[x].son[0]=S[x].f=S[x].sub=S[x].v=0;
if(x==-wz)_wz--;
}
inline void S_update(ll x){
if(x){
S[x].sub=S[x].cnt;
if(S[x].son[0])S[x].sub+=S[S[x].son[0]].sub;
if(S[x].son[1])S[x].sub+=S[S[x].son[1]].sub;
}
}
inline void S_rotate(ll x){
ll fnow=S[x].f,ffnow=S[fnow].f;
bool w=S_which(x);
S[fnow].son[w]=S[x].son[w^1];
S[S[fnow].son[w]].f=fnow;
S[fnow].f=x;
S[x].f=ffnow;
S[x].son[w^1]=fnow;
if(ffnow){
S[ffnow].son[S[ffnow].son[1]==fnow]=x;
}
S_update(fnow);
}
inline void S_splay(ll x,ll goal){
for(ll qwq;(qwq=S[x].f)!=goal;S_rotate(x)){
if(S[qwq].f!=goal){
S_rotate(S_which(x)==S_which(qwq)?qwq:x);
}
}
if(goal==0){

_root=x;
}
}
inline void S_insert(ll x){
if(!_root){
_wz++;
S[_wz].son[0]=S[_wz].son[1]=S[_wz].f=0;
_root=_wz;
S[_wz].sub=S[_wz].cnt++;
S[_wz].v=x;
return ;
}
_now=_root,_fa=0;
while(1){
if(x==S[_now].v){
S[_now].cnt++;
S_update(_now);
S_update(_fa);
S_splay(_now,0);
break;
}
_fa=_now;
_now=S[_now].son[S[_now].v<x];
if(!_now){
_wz++;
S[_wz].son[0]=S[_wz].son[1]=0;
S[_wz].f=_fa;
S[_wz].sub=S[_wz].cnt++;
S[_fa].son[S[_fa].v<x]=_wz;
S[_wz].v=x;
S_update(_fa);
S_splay(_wz,0);
break;
}
}
}
inline ll S_find_pre(){
_now=S[_root].son[0];
while(S[_now].son[1]){
_now=S[_now].son[1];
}
return _now;
}
inline ll S_find_rank(ll x){
_now=_root,_rank=0;
while(1){
if(x<S[_now].v){
_now=S[_now].son[0];
}
else {
_rank+=(S[_now].son[0]?S[S[_now].son[0]].sub:0);
if(x==S[_now].v){
S_splay(_now,0);
return _rank+1;
}
_rank+=S[_now].cnt;
_now=S[_now].son[1];
}
}

}
inline ll S_find_num(ll x){
_now=_root;
while(1){
if(S[_now].son[0]&&x<=S[S[_now].son[0]].sub){
_now=S[_now].son[0];
}
else {
ll temp=(S[_now].son[0]?S[S[_now].son[0]].sub:0)+S[_now].cnt;
if(x<=temp)return S[_now].v;
x-=temp;
_now=S[_now].son[1];
}
}
}
inline void S_delete(ll x){
int hhh=S_find_rank(x);
if(S[_root].cnt>1){
S[_root].cnt--;
S_update(_root);
return ;
}
if(!S[_root].son[0]&&!S[_root].son[1]){
S_clear(_root);
_root=0;
return ;
}
if(!S[_root].son[0]){
_old_root=_root;
_root=S[_root].son[1];
S[_root].f=0;
S_clear(_old_root);
return ;
}
if(!S[_root].son[1]){
_old_root=_root;
_root=S[_root].son[0];
S[_root].f=0;
S_clear(_old_root);
return ;
}
int left_max=S_find_pre(),_old_root=_root;
S_splay(left_max,0);
S[_root].son[1]=S[_old_root].son[1];
S[S[_old_root].son[1]].f=_root;
S_clear(_old_root);
S_update(_root);
}

/*___________________________________________________________*/

int main(){
ll a,n,m,b;
char s[20];
cin>>n>>m;
insert(Inf);
insert(-Inf);
for(i=1;i<=n;i++){
if(i!=1)S_insert(my_abs(base[i-1]-base[i]));
init_insert(base[i]);
}
for(register int i=1;i<=m;i++){
scanf("%s",s);
int ss=strlen(s);
if(ss==7) {
printf("%d\n",S_find_num(1));
continue;
}
else if(ss==12){
printf("%d\n",minn);
continue;
}
else {
}