如果我说我······不擅长左偏树······你们会信吗?
查看原帖
如果我说我······不擅长左偏树······你们会信吗?
472950
封禁用户楼主2022/4/8 16:40

不扯了:

wee\color{white}\texttt{wee}

#include<bits/stdc++.h>
#define int long long
using namespace std;

struct A{
	int bad,id;
	bool operator<(const A&r)const{
		if(bad!=r.bad)return bad<r.bad;
		return id>r.id;
	}
};

struct V{
	A ver;
	int l,r,fa,lz;
	V(){
		l=r=fa=-1;
		lz=0;
	}
}v[100005];

int t,n,m,k,w;
bool ct[100005];

int Find(int xx){
	return v[xx].fa==-1?xx:Find(v[xx].fa);
}

void Zig(int xx){
	v[xx].lz=(v[xx].l==-1||v[xx].r==-1)?0:(min(v[v[xx].l].lz,v[v[xx].r].lz)+1);
	if(v[xx].l==-1)swap(v[xx].l,v[xx].r);
	else if(v[xx].r!=-1&&v[v[xx].l].lz<v[v[xx].r].lz)swap(v[xx].l,v[xx].r);
}

int Combine(int xx,int yy){
	if(v[xx].ver<v[yy].ver)swap(xx,yy);
	if(v[xx].r==-1){
		v[xx].r=yy;
		v[yy].fa=xx;
	}
	else{
		v[xx].r=Combine(v[xx].r,yy);
		v[v[xx].r].fa=xx;
	}
	Zig(xx);
	return xx;
}

void Refresh(int xx,int b){
	int yx=v[xx].fa;
	v[xx].fa=-1;
	v[xx].ver.bad=b;
	if(v[xx].l!=-1&&v[xx].r!=-1){
		v[xx].l=v[xx].r=-1;
		v[v[xx].l].fa=v[v[xx].r].fa=-1;
		v[Combine(Combine(v[xx].l,v[xx].r),xx)].fa=yx;
	}
	else if(v[xx].l!=-1){
		v[xx].l=-1;
		v[v[xx].l].fa=-1;
		v[Combine(xx,v[xx].l)].fa=yx;
	}
	else v[xx].fa=yx;
}

void Restart_and_Input(){
	for(int i=1;i<=n;i++){
		v[i]=V();
		scanf("%lld",&v[i].ver.bad);
		v[i].ver.id=i;
		ct[i]=0;
	}
}

void Work_and_Output(){
	while(m--){
		int op,a,b;
		scanf("%lld%lld",&op,&a);
		if(op==2)Refresh(a,0);
		if(op==3){
			scanf("%lld",&b);
			int rt=Find(a);
			Refresh(rt,max(0ll,v[rt].ver.bad-b));
		}
		if(op==4){
			scanf("%lld",&b);
			int ra=Find(a),rb=Find(b);
			if(ra!=rb)Combine(ra,rb);
		}
	}
	int ans=0,mxm=0;
	for(int i=1;i<=n;i++){
		int rt=Find(i);
		if(!ct[rt]){
			ct[rt]=1;
			ans+=v[rt].ver.bad;
			mxm=max(mxm,v[rt].ver.bad);
		}
	}
	if(w==2)ans-=mxm;
	if(w==3)ans+=mxm;
	if(ans==0)printf("Gensokyo ");
	else if(ans>k)printf("Hell ");
	else printf("Heaven ");
	printf("%lld\n",ans);
}

signed main(){
	scanf("%lld%lld%lld",&t,&w,&k);
	while(t--){
		scanf("%lld%lld",&n,&m);
		Restart_and_Input();
		Work_and_Output();
	}
	return 0;
}

一个点没过,大红大紫大黑······救救我吧!

2022/4/8 16:40
加载中...