社区讨论
这种奇怪的情况你们遇到过没有
P3369【模板】普通平衡树参与者 16已保存回复 31
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 31 条
- 当前快照
- 1 份
- 快照标识符
- @mi5hlzq4
- 此快照首次捕获于
- 2025/11/19 12:13 4 个月前
- 此快照最后确认于
- 2025/11/19 12:42 4 个月前
就是老是MLE或者RE,改大数组反而AC某些点,改小了又可以AC另一些点,而且改点完全无关紧要的东西都可以导致几个点能不能A。
求大神帮忙看看为什么?
CPP#include<bits/stdc++.h>
using namespace std;
const int maxn=10064;
inline int read()
{
int x=0,f=1;char ch;
for(ch=getchar();ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}
struct node
{
int key,ch[2],cnt,size,fa;
}T[maxn];
int root,num=0,n;
void create(int x)
{
num++;
T[num].key=x;
T[num].size=T[num].cnt=1;
T[num].ch[0]=T[num].ch[1]=-1;
}
void update(int u)
{
if(u==-1)return;
T[u].size=T[u].cnt;
if(T[u].ch[0]!=-1)T[u].size+=T[T[u].ch[0]].size;
if(T[u].ch[1]!=-1)T[u].size+=T[T[u].ch[1]].size;
}
int getpos(int u){return (u==T[T[u].fa].ch[1]);}
void rotate(int u)
{
int fa=T[u].fa,fafa=T[fa].fa,k=getpos(u);
T[fa].ch[k]=T[u].ch[k^1];
T[T[u].ch[k^1]].fa=T[u].fa;
T[u].ch[k^1]=fa;
T[fa].fa=u;
T[u].fa=fafa;
if(fafa!=-1)T[fafa].ch[T[fafa].ch[1]==fa]=u;
update(fa);
update(u);
}
void Splay(int u)
{
for(int fa;(fa=T[u].fa)!=-1;rotate(u))
if(T[fa].fa!=-1)rotate(getpos(u)==getpos(fa)?fa:u);
root=u;
}
void insert(int x)
{
if(root==-1)
{
create(x);
T[num].fa=-1;
root=num;
return;
}
int p=root,fa=-1;
while(1)
{
if(x==T[p].key)
{
T[p].cnt++;
update(p);update(fa);
Splay(p);
return;
}
fa=p;p=T[p].ch[x>T[fa].key];
if(p==-1)
{
create(x);
T[num].fa=fa;
T[fa].ch[x>T[fa].key]=num;
update(fa);
Splay(num);
return;
}
}
}
int find(int x)
{
int p=root,sum=0;
while(1)
{
if(x<T[p].key)p=T[p].ch[0];
else
{
sum+=(T[p].ch[0]==-1?0:T[T[p].ch[0]].size);
if(x==T[p].key)
{
Splay(p);
return sum+1;
}
sum+=T[p].cnt;
p=T[p].ch[1];
}
}
}
int pre()
{
int p=T[root].ch[0];
while(T[p].ch[1]!=-1)p=T[p].ch[1];
return p;
}
int next()
{
int p=T[root].ch[1];
while(T[p].ch[0]!=-1)p=T[p].ch[0];
return p;
}
void del(int x)
{
find(x);
if(T[root].cnt>1){T[root].cnt--;update(root);return;}
if(T[root].ch[0]==-1&&T[root].ch[1]==-1){root=-1;return;}
if(T[root].ch[0]==-1){root=T[root].ch[1];T[root].fa=-1;return;}
else if(T[root].ch[1]==-1){root=T[root].ch[0];T[root].fa=-1;return;}
int p=pre(),temp=root;
Splay(p);
T[T[temp].ch[1]].fa=root;
T[root].ch[1]=T[temp].ch[1];
update(root);
}
int get_pos(int x)
{
int p=root;
while(1)
{
if(T[p].ch[0]!=-1&&x<=T[T[p].ch[0]].size)p=T[p].ch[0];
else
{
int temp=(T[p].ch[0]!=-1?T[T[p].ch[0]].size:0)+T[p].cnt;
if(x<=temp)return T[p].key;
x-=temp;
p=T[p].ch[1];
}
}
}
int main()
{
n=read();root=-1;
while(n--)
{
int opt,x;
opt=read();x=read();
switch(opt)
{
case 1:insert(x);break;
case 2:del(x);break;
case 3:printf("%d\n",find(x));break;
case 4:printf("%d\n",get_pos(x));break;
case 5:insert(x);printf("%d\n",T[pre()].key);del(x);break;
case 6:insert(x);printf("%d\n",T[next()].key);del(x);break;
}
}
return 0;
}
回复
共 31 条回复,欢迎继续交流。
正在加载回复...