求助splay
查看原帖
求助splay
26906
stone_heart楼主2021/8/13 14:58

后七个点全T了,是我splay的姿势不对么(

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

char Name[500][15];int n,m,q;

struct S_Play{
	
	int siz[100005],f[100005],ch[2][100005],tot=0,rot=1;
	char name[100005][15];
	
	inline void push_up(int x){siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+1;}
	
	inline void rotate(int x){
		int y=f[x],z=f[y],k=ch[1][y]==x;
		f[x]=z;ch[ch[1][z]==y][z]=x;
		f[ch[k^1][x]]=y;ch[k][y]=ch[k^1][x];
		f[y]=x;ch[k^1][x]=y;
		push_up(y);push_up(x);
	}
	
	inline void splay(int x,int goal){
		while(f[x]!=goal){
			int y=f[x],z=f[y];
			if(z!=goal)
				((ch[1][y]==x)^(ch[1][z]==y))?rotate(x):rotate(y);
			rotate(x);
		}
		if(goal==0)rot=x;
	}
	
	int build(int l,int r,int pre){
		if(l>r)return 0;
		int mid=l+r>>1,u=++tot,g=0;
		while(Name[mid][g]){name[u][g]=Name[mid][g];g++;}f[u]=pre;
		ch[0][u]=build(l,mid-1,u);
		ch[1][u]=build(mid+1,r,u);
		push_up(u);
		return u;
	}
	
	inline int kth(int k){
		int u=rot;
		while(1){
			if(siz[ch[0][u]]>=k)u=ch[0][u];
			else{
				k-=siz[ch[0][u]];
				if(k==1)return u;
				k--;u=ch[1][u];
			}
		}
	}
	
	inline void insert(int k,char s[15]){
		int x=kth(k-1),y=kth(k);
		splay(x,0);splay(y,x);
		int u=++tot;
		ch[0][y]=u;
		for(int g=0;s[g];g++)name[u][g]=s[g];
		siz[u]=1;f[u]=y;
		splay(u,0);
	}
	
	inline void print(int x){
		if(ch[0][x])print(ch[0][x]);
		printf("%s ",name[x]);
		if(ch[1][x])print(ch[1][x]);
	}
	
}t;

int main(){
	
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%s",Name[i+1]);
	t.build(1,n+2,0);
	scanf("%d",&m);
	while(m--){
		int k;char s[15];
		scanf("%s %d",s,&k);
		t.insert(min(k+2,t.tot),s);
	}
	scanf("%d",&q);
	while(q--){
		int k;
		scanf("%d",&k);
		printf("%s\n",t.name[t.kth(k+2)]);
	}
	
	return 0;
	
}
2021/8/13 14:58
加载中...