我发现一个获得关注的方法 违规紫砂
  • 板块灌水区
  • 楼主lovecjj
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/2/7 17:45
  • 上次更新2025/2/7 20:28:05
查看原帖
我发现一个获得关注的方法 违规紫砂
1405686
lovecjj楼主2025/2/7 17:45

帮我调出这个代码,你就能得到一个关注

P3369 【模板】普通平衡树

only wa on 13

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=3e5+110;
const int Mod=4e7+110;
mt19937_64 Rand(20100123);
int Read(){
	int sum=0,k=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')k=-2;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum=sum*10+c-48;
		c=getchar();
	}return sum*k;
}
struct Tree_Node{
	int lz,rz;
	int Val,Nval;
	int Size;
}t[M];
void Update(int u){t[u].Size=t[t[u].lz].Size+t[t[u].rz].Size+1;}
int Sum=0;
int Get_Node(int val){
	t[++Sum].Val=val;
	t[Sum].Size=1;
	t[Sum].Nval=Rand();
	return Sum;
}
int Roxt,Royt,Rozt;
void Val_Split(int Now,int val,int &Roxt,int &Royt){//权值分裂 
	if(Now==0){
		Royt=Roxt=0;
		return ;
	}
	if(t[Now].Val<=val){
		Roxt=Now;
		Val_Split(t[Now].rz,val,t[Now].rz,Royt);
	}
	else{
		Royt=Now;
		Val_Split(t[Now].lz,val,Roxt,t[Now].lz);
	}
	Update(Now);
}
void Rand_Split(int Now,int Num,int &Roxt,int &Royt){
	if(Now==0){
		Royt=Roxt=0;
		return;
	}
	if(Num<=t[t[Now].lz].Size){
		Royt=Now;
		Rand_Split(t[Now].lz,Now,Roxt,t[Now].lz);
	}
	else{
		Roxt=Now;
		Rand_Split(t[Now].rz,Num-t[t[Now].lz].Size-1,t[Now].rz,Royt);
	}
	Update(Now);
}

int Merge(int u,int v){
	if(u==0||v==0) return u+v;
	if(t[u].Nval<t[v].Nval){
		t[u].rz=Merge(t[u].rz,v);
		Update(u);
		return u;
	}
	else{
		t[v].lz=Merge(u,t[v].lz);
		Update(v);
		return v;
	}
}
int Root;
void Insert(int val){
	Val_Split(Root,val,Roxt,Royt);
	Root=Merge(Merge(Roxt,Get_Node(val)),Royt);
	return ;
}
void Group_Delete(int val){
	Val_Split(Root,val,Roxt,Rozt);
	Val_Split(Roxt,val-1,Roxt,Royt);
	Root=Merge(Roxt,Rozt);
}
void Single_Delete(int val){
	Val_Split(Root,val,Roxt,Rozt);
	Val_Split(Roxt,val-1,Roxt,Royt);
	Royt=Merge(t[Royt].lz,t[Royt].rz);
	Root=Merge(Merge(Roxt,Royt),Rozt);
}
int Find_Kth(int Rot,int k){
	int Now=Rot;
	for(int i=1;i>=0;i++){
		if(k<=t[t[Now].lz].Size) Now=t[Now].lz;
		else if(k==t[t[Now].lz].Size+1) return t[Now].Val;
			else{
				k=k-t[t[Now].lz].Size-1;
				Now=t[Now].rz;
			}
	}
}
int Find_Rank(int val){
	Val_Split(Root,val-1,Roxt,Royt);
	int Res=t[Roxt].Size+1;
	Root=Merge(Roxt,Royt);
	return Res;
}
int Find_From(int val){
	
	Val_Split(Root,val-1,Roxt,Royt);
	int Ans=Find_Kth(Roxt,t[Roxt].Size);
	Root=Merge(Roxt,Royt);
	return Ans;
}
int Find_Next(int val){
	Val_Split(Root,val,Roxt,Royt);
	int Ans=Find_Kth(Royt,1);
	Root=Merge(Roxt,Royt);
	return Ans;
}
signed main(){
//	freopen("in.in", "r", stdin);
//    freopen("std.txt", "w", stdout);
	int n=Read();
//	Insert(0x3f3f3f3f);
//	Insert(-0x3f3f3f3f);
	for(int i=1;i<=n;i++){
		int opt=Read(),x=Read();
		if(opt==1){
			Insert(x);
			continue;
		}
		if(opt==2){
			Single_Delete(x);
			continue;
		}
		if(opt==3){
			Insert(x);
			cout<<Find_Rank(x)<<endl;
			Single_Delete(x);
			continue;
		}
		if(opt==4){
			Insert(x);
			cout<<Find_Kth(Root,x+1)<<endl;
			Single_Delete(x);
			continue;
		}
		if(opt==5){
			Insert(x);
			cout<<Find_From(x)<<endl;
			Single_Delete(x);
			continue;
		}
		if(opt==6){
			Insert(x);
			cout<<Find_Next(x)<<endl;
			Single_Delete(x);
			continue;
		}
	}
	return 0;
}
2025/2/7 17:45
加载中...