P2234 [HNOI]营业额统计
皎月半洒花
2018-04-25 16:48:37
就是个二叉搜索树的水题……让我用$Splay$给过了……
不过以后需要注意的一点是，在找前驱后继的时候,对于这个题一定要是下标不为$0$,而不是权值不为$0$,因为是可以有负数的。
(*￣m￣)我就因为这个一直$90$分……也不知道为什么数据这么水$qwq$
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define MAXN 1000007
int f[MAXN],cnt[MAXN],value[MAXN],sons[MAXN][2],sub_size[MAXN],whole_size,root;
inline void S_Clear(int x){
sons[x][0]=sons[x][1]=f[x]=sub_size[x]=cnt[x]=value[x]=0;
return ;
}
inline bool get_which(int x){
return sons[f[x]][1]==x;
}
inline void update(int x){
sub_size[x]=cnt[x];
if (sons[x][0]) sub_size[x]+=sub_size[sons[x][0]];
if (sons[x][1]) sub_size[x]+=sub_size[sons[x][1]];
return ;
}
inline void rotate(int x){
int father=f[x],g_father=f[father],which_son=get_which(x);
sons[father][which_son]=sons[x][!which_son];
f[sons[father][which_son]]=father;
sons[x][!which_son]=father;
f[father]=x;
f[x]=g_father;
if(g_father){
sons[g_father][sons[g_father][1]==father]=x;
}
update(father);
update(x);
return ;
}
inline void splay(int x){
for (int fa;fa=f[x];rotate(x))
if (f[fa])
rotate((get_which(x)==get_which(fa))?fa:x);
root=x;
return ;
}
inline void insert(int x){
if(!root){
whole_size++;
sons[whole_size][0]=sons[whole_size][1]=f[whole_size]=0;
root=whole_size;
sub_size[whole_size]=cnt[whole_size]++;
value[whole_size]=x;
return ;
}
int now=root,fa=0;
while(1){
if(x==value[now]){
cnt[now]++;
update(now);
update(fa);
splay(now);
break;
}
fa=now;
now=sons[now][value[now]<x];
if(!now){
whole_size++;
sons[whole_size][0]=sons[whole_size][1]=0;
f[whole_size]=fa;
sub_size[whole_size]=cnt[whole_size]=1;
sons[fa][value[fa]<x]=whole_size;
value[whole_size]=x;
update(fa);
splay(whole_size);
break;
}
}
return ;
}
inline int find_pre(){
int now=sons[root][0];
if(!now)return now;
while(sons[now][1])now=sons[now][1];
return now;
}
inline int find_suffix(){
int now=sons[root][1];
if(!now)return now;
while(sons[now][0])now=sons[now][0];
return now;
}
inline int abs(int n){
return n>=0?n:-n;
}
int main(){
int n,a;
cin>>n;
cin>>a;
insert(a);
int sum=a;
for(int i=2;i<=n;i++){
cin>>a;
insert(a);
if(cnt[root]>=2)continue;
int pre=find_pre(),minn=90909090;
int suffix=find_suffix();
if(pre)minn=min(abs(value[pre]-a),minn);
if(suffix)minn=min(abs(value[suffix]-a),minn);
sum+=minn;
}
cout<<sum;
return 0;
}
```