RT

https://www.luogu.com.cn/problem/P3369

救命，只有第11个点第2问（问前驱），没找到了，救救孩子。

会其他的平衡树，突发奇想写写替罪羊练练手，然后就坐牢了。

没有写合并相同节点，选择手写动态回收内存。

问题在第11个数据点，第2问找前驱时输出了0（完全没找到），答案输出了负值。

下不了数据非常的折磨。

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    int le,ri;//左，右儿子
    int key;//关键值
    int cNt;//记录子树大小
}node[100100];//alpha现场计算
//如果你想写封装，那就写，主要是如果封装你要把一个树看作一个整体，不然写了根没写一样，可以考虑封装Splay或者FHQ，但是替罪羊真没必要
const double liMiT=0.75;
int root;//0就是目标点辣！
int head;//栈头，实现动态分配空间
int mAllcer[100100];//栈
int rEc;//记录最大重构树
int keyPark[100100];//reBuild的暂时停车场
int sTack_out()
{
    node[mAllcer[head]].le=0;
    node[mAllcer[head]].ri=0;
    node[mAllcer[head]].cNt=0;
    return mAllcer[head--];
}
void sTack_in(int poi)
{
    mAllcer[++head]=poi;
    return;
}
void pushup(int poi)
{
    node[poi].cNt=node[node[poi].le].cNt+node[node[poi].ri].cNt+1;
    return;
}
bool pan(int poi)
{
    double aLpha=double(max(node[node[poi].le].cNt,node[node[poi].ri].cNt))/double(node[poi].cNt);
    return aLpha>liMiT;
}
void Insert(int kEy,int poi)//poi for position
{
    if(kEy<node[poi].key)
    {
        if(node[poi].le==0)
        {
            node[poi].le=sTack_out();
            node[node[poi].le].key=kEy;
            node[node[poi].le].cNt=1;
        }
        else
        {
            Insert(kEy,node[poi].le);
        }
    }
    else
    {
        if(node[poi].ri==0)
        {
            node[poi].ri=sTack_out();
            node[node[poi].ri].key=kEy;
            node[node[poi].ri].cNt=1;
        }
        else
        {
            Insert(kEy,node[poi].ri);
        }
    }
    pushup(poi);
    if(pan(poi))
    {
        rEc=poi;
    }
    return;
}
int pArk_cnt;//停车场数组的计数器
void dfs_pArk(int poi)
{
    if(node[poi].le!=0)
    {
        dfs_pArk(node[poi].le);
        sTack_in(node[poi].le);
    }
    pArk_cnt++;
    keyPark[pArk_cnt]=node[poi].key;
    if(node[poi].ri!=0)
    {
        dfs_pArk(node[poi].ri);
        sTack_in(node[poi].ri);
    }
    return;
}
void build(int l,int r,int poi)//注意我们的rebuild方式无法保证相同的元素大小顺序关系
{
    int mid=(l+r)/2;
    node[poi].key=keyPark[mid];
    node[poi].cNt=1;
    if(l<=mid-1)
    {
        node[poi].le=sTack_out();
        build(l,mid-1,node[poi].le);
    }
    if(mid+1<=r)
    {
        node[poi].ri=sTack_out();
        build(mid+1,r,node[poi].ri);
    }
    pushup(poi);
    return;
}
//左子树：相同/比父节点小的
//右子树：相同/比父节点大的
void reBuild(int poi)
{
    if(poi==0)return;
    pArk_cnt=0;
    dfs_pArk(poi);
    //接树的时候注意这个函数的poi不会被回收掉，poi就是新树的根！
    //按照这个写法只能这样，因为上面的树还连接着poi；
    node[poi].le=0;
    node[poi].ri=0;
    //切断连接
    build(1,pArk_cnt,poi);
    // pushup(poi);
    return;
}
void sTack_init(int num)
{
    for(int i=1;i<=num;i++)
    {
        sTack_in(i);
    }
    return;
}
// int Merge(int l,int r)
// {
//     if(!l||!r)
//     {
//         return l+r;
//     }
//     int a=rand();
//     int b=rand();
//     int poi;
//     if(a>b)
//     {
//         poi=Merge(node[l].ri,r);
//         node[l].ri=poi;
//     }
//     else
//     {
//         poi=Merge(node[r].le,l);
//         node[r].le=poi;
//     }
//     pushup(poi);
//     if(pan(poi))rEc=poi;
//     return poi;
// }
int Merge(int l,int r)
{
    if(!l||!r)
    {
        return l+r;
    }
    int a=rand();
    int b=rand();
    if(a<b)
    {
        node[l].ri=Merge(node[l].ri,r);
        pushup(l);
        if(pan(l))rEc=l;
        return l;
    }
    else
    {
        node[r].le=Merge(l,node[r].le);
        pushup(r);
        if(pan(r))rEc=r;
        return r;
    }
}
void Dlete(int kEy,int poi,int fat,bool pan)//可以写懒惰删除，但是感觉懒惰删除好low
{
    if(poi==0)return;//题设肯定存在，只是万一错误操作。。。我写一个在这里
    if(node[poi].key==kEy)
    {
        //1.在poi处合并两颗子树，fhq_treap的merge()操作
        //2.把左树直接放在右树的叶节点并且重新统计并重构
        //根节点被删掉就完力！
        if(fat==0)
        {
            root=Merge(node[poi].le,node[poi].ri);
            // pushup(root);
            sTack_in(poi);
            return;
        }
        if(pan==0)
        {
            node[fat].le=Merge(node[poi].le,node[poi].ri);
        }
        else
        {
            node[fat].ri=Merge(node[poi].le,node[poi].ri);
        }
        sTack_in(poi);
        return;
    }
    if(kEy<node[poi].key)
    {
        Dlete(kEy,node[poi].le,poi,0);
        pushup(poi);
    }
    else
    {
        Dlete(kEy,node[poi].ri,poi,1);
        pushup(poi);
    }
    return;
}
void rAnk(int kEy,int poi)
{
    if(kEy==node[node[poi].le].cNt+1)
    {
        printf("%d\n",node[poi].key);
        // printf("f\n");
        return;
    }
    if(kEy<node[node[poi].le].cNt+1)
    {
        rAnk(kEy,node[poi].le);
    }
    else
    {
        rAnk(kEy-node[node[poi].le].cNt-1,node[poi].ri);
    }
    return;
}
void FindRank(int kEy,int poi,int ans)//因为reBuild方式，所以不得不这样
{
    if(poi==0)
    {
        printf("%d\n",ans+1);
        return;
    }
    if(node[poi].key<kEy)
    {
        ans+=node[node[poi].le].cNt+1;
        FindRank(kEy,node[poi].ri,ans);
    }
    else
    {
        FindRank(kEy,node[poi].le,ans);
    }
    return;
}
void fro_Num(int kEy,int poi,int ans)//数据正常，有前驱的情况下
{
    if(poi==0)
    {
        printf("%d\n",node[ans].key);
        // printf("f\n");
        return;
    }
    if(node[poi].key<kEy)
    {
        fro_Num(kEy,node[poi].ri,poi);
    }
    else
    {
        fro_Num(kEy,node[poi].le,ans);
    }
    return;
}
//fro_Num
void bac_Num(int kEy,int poi,int ans)//数据正常，有前驱的情况下
{
    if(poi==0)
    {
        printf("%d\n",node[ans].key);
        return;
    }
    if(node[poi].key<=kEy)
    {
        bac_Num(kEy,node[poi].ri,ans);
    }
    else
    {
        bac_Num(kEy,node[poi].le,poi);
    }
    return;
}
// int cont;
// void dfs_out(int poi)
// {
//     if(poi==0)
//     {
//         return;
//     }
//     dfs_out(node[poi].le);
//     printf("%d ",node[poi].key);
//     cont++;
//     dfs_out(node[poi].ri);
//     return;
// }
int main()
{
    // freopen("input","r",stdin);
    // freopen("ans","w",stdout);
    srand(time(0));
    int num,opt,kEy;
    scanf("%d",&num);
    sTack_init(num);
    scanf("%d %d",&opt,&kEy);
    if(opt==1)
    {
        root=sTack_out();
        node[root].key=kEy;
        node[root].cNt=1;
    }
    for(int i=1;i<num;i++)
    {
        scanf("%d %d",&opt,&kEy);
        switch (opt)
        {
        case 1:
            rEc=0;
            Insert(kEy,root);
            reBuild(rEc);
            break;
        case 2:
            rEc=0;
            Dlete(kEy,root,0,0);
            reBuild(rEc);
            break;
        case 3:
            FindRank(kEy,root,0);//
            break;
        case 4:
            rAnk(kEy,root);
            break;
        case 5:
            fro_Num(kEy,root,0);
            break;
        case 6:
            bac_Num(kEy,root,0);
        default:
            break;
        }
    }
    // dfs_out(root);
    // printf("\n%d\n",cont);
    return 0;
}
//1,2,4操作无问题