求助fhq最大,小值维护
查看原帖
求助fhq最大,小值维护
233198
starseven楼主2020/5/16 15:23

为什么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;
}

只能对一个点

2020/5/16 15:23
加载中...