社区讨论

初学OI,妹子,已经不会写Splay了QwQ,求差错

P1486[NOI2004] 郁闷的出纳员参与者 13已保存回复 21

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
21 条
当前快照
1 份
快照标识符
@mi868oim
此快照首次捕获于
2025/11/21 09:18
4 个月前
此快照最后确认于
2025/11/21 10:00
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>

using namespace std;

#define MAXN 100010
#define LL long long

inline int read()
{
    int f=1,x=0;
    char ch;
    do
    {
        ch=getchar();
        if(ch=='-') f=-1;
    }while(ch<'0'||ch>'9');
    do
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }while(ch>='0'&&ch<='9');
    return f*x;
} 

int n,minn,ans;

struct Splay
{
	int ch[MAXN][2];
	int fa[MAXN];
	int cnt[MAXN];
	int sz[MAXN];
	int val[MAXN];
	int idx;
	int root;
	inline int chk(int x)
	{
		return x==ch[fa[x]][1];
	}
	inline void pushup(int x)
	{
		sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
	}
	inline void rotate(int x)
	{
		int f=fa[x],gf=fa[f];
		int k=chk(x);
		ch[gf][chk(f)]=x;fa[x]=gf;
		ch[f][k]=ch[x][k^1];fa[ch[x][k^1]]=f;
		ch[x][k^1]=f;fa[f]=x;
	   pushup(f);pushup(x);
	} 
	inline void splay(int x,int goal)
	{

		while(fa[x]!=goal)
		{		
			int f=fa[x],gf=fa[f];
			if(gf!=goal)
			{
				if(chk(x)==chk(f)) rotate(f);
				else rotate(x);
			}
			rotate(x);
		}
		if(!goal) root=x;
	}
	inline void add(int x)
	{
		for(int i=1;i<=idx;i++) val[i]+=x;
	}
	inline void insert(int x)
	{
		if(x<minn) return;
		int cur=root,f=0;
		while(cur&&val[cur]!=x)
		{
			f=cur;
			if(val[cur]>x) cur=ch[cur][0];
			else cur=ch[cur][1];
		}
		if(val[cur]==x&&!cur)
		{
			cnt[cur]++;
			splay(cur,0);
		}
		else
		{
			cur=++idx;
			if(f) ch[f][val[f]<x]=cur;
			sz[cur]=1;cnt[cur]=1;val[cur]=x;
			fa[cur]=f;
			ch[cur][0]=ch[cur][1]=0;
			splay(cur,0);
		}
	}
	inline int kth(int k)
	{
		if(k>=sz[root]) return -1;
		k++;
		int cur=root;
		while(1)
		{
			if(ch[cur][1]&&k<=sz[ch[cur][1]]) cur=ch[cur][1];
			else if(k<=sz[ch[cur][1]]+cnt[cur]&&k>sz[ch[cur][1]]) return val[cur];
			else k-=sz[ch[cur][1]]+cnt[cur],cur=ch[cur][0];
		}
	}
	inline void find(int x)
	{
		if(!root) return;
		int cur=root;
		while(x!=val[cur]&&ch[cur][x>val[cur]])
		{
			cur=ch[cur][x>val[cur]];
		}
		splay(cur,0);
	}
	inline int pre(int x)
	{
		find(x);
		if(val[root]>x) return root;
		int cur=ch[root][0];
		while(ch[cur][1])
		{
			cur=ch[cur][1];
		}
		return cur;
	}
	inline int succ(int x)
	{
		find(x);
		if(val[root]>=x) return root;
		int cur=ch[root][1];
		while(ch[cur][0])
		{
			cur=ch[cur][0];
		}
		return cur;
	}
	inline void remove(int x)
	{
		int now=succ(x+minn);
		splay(now,0);
		ans+=sz[ch[root][0]];
		ch[root][0]=0;
		pushup(root);
		add(-1*x);
	}

}tree;

int main()
{
	n=read();minn=read();
	tree.insert(1<<30);
	for(int i=1;i<=n;i++)
	{
		char opt;
		scanf("%c",&opt);
		int x=read();
		if(opt=='I')
		{
			tree.insert(x);
		}
		if(opt=='A')
		{
			tree.add(x);
		}
		if(opt=='S')
		{
			tree.remove(x);
		}
		if(opt=='F')
		{
			printf("%d\n",tree.kth(x));
		}
	}
	cout<<ans<<endl;
}
第一个数据
CPP
20 0
I 4
F 1
I 6
S 9
F 14
I 6
I 7
A 8
I 3
F 2
I 9
I 6
I 6
S 3
S 5
I 6
F 1
I 3
A 2
F 5

都过不了。。。

回复

21 条回复,欢迎继续交流。

正在加载回复...