为什么fhq只能够用查询前驱和后驱的方法来找最大值和最小值,而不能用maxn和minn维护?
#include<cstdio>
#include<iostream>
#include<ctime>
#include<cstdlib>
#define ri register int
#define Starseven main
using namespace std;
int n,ans,root,cnt;
struct node{
int son[2],va,maxn,minn,rd,size;
}tr[32769];
int abs(int x){return (x<0)?-x:x;}
#define ls tr[now].son[0]
#define rs tr[now].son[1]
void Pushup(int now){
tr[now].maxn=tr[now].va;tr[now].minn=tr[now].va;
if(ls) tr[now].maxn=max(tr[now].maxn,tr[ls].maxn),tr[now].minn=min(tr[now].minn,tr[ls].minn);
if(rs) tr[now].maxn=max(tr[now].maxn,tr[rs].maxn),tr[now].minn=min(tr[now].minn,tr[rs].minn);
tr[now].size=tr[ls].size+tr[rs].size+1;
return ;
}
void Split(int now,int k,int &x,int &y){
if(!now){x=y=0;return ;}
if(tr[now].va<=k)
x=now,Split(tr[now].son[1],k,tr[now].son[1],y);
else y=now,Split(tr[now].son[0],k,x,tr[now].son[0]);
Pushup(now);
}
int New_code(int v){
tr[++cnt].va=tr[cnt].maxn=tr[cnt].minn=v;
tr[cnt].rd=rand();
tr[cnt].size=1;
return cnt;
}
int Merge(int x,int y){
if(!x||!y) return x+y;
if(tr[x].rd<tr[y].rd){
tr[x].son[1]=Merge(tr[x].son[1],y),Pushup(x);
return x;
}
else{
tr[y].son[0]=Merge(x,tr[y].son[0]),Pushup(y);
return y;
}
}
int Starseven(void){
srand(0);
cin>>n;
int a,x,y;
cin>>a;
Split(root,a,x,y);
root=Merge(Merge(x,New_code(a)),y);
ans+=a;
n--;
while(n--){
cin>>a;
Split(root,a,x,y);
int add=999999999;
if(tr[x].size) add=min(add,abs(tr[x].maxn-a));
if(tr[y].size) add=min(add,abs(tr[y].minn-a));
ans+=add;
root=Merge(Merge(x,New_code(a)),y);
}
cout<<ans<<endl;
return 0;
}
只能对一个点