社区讨论
初学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;
}
第一个数据
CPP20 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 条回复,欢迎继续交流。
正在加载回复...