社区讨论

这种奇怪的情况你们遇到过没有

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 条回复,欢迎继续交流。

正在加载回复...