蒟蒻刚学OI,请问本题最后一组数据卡的是什么?

回复帖子

@zhyyng 2019-02-11 22:50 回复

蒟蒻刚学替罪羊树,结果最后一个点T飞了。

这里想问一下最后一个点卡的是哪里的问题? 附代码:

#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
inline int getint()
{
    register int r=0,f=1;
    register char c=getchar();
    while (!isdigit(c))
        f=c=='-'?-f:f,c=getchar();
    while (isdigit(c))
        r=(r<<3)+(r<<1)+(c^48),c=getchar();
    return r*f;
}
const int N=1e5+10;
const double alpha=0.75;
int n;
struct Node;
Node *nil;
struct Node
{
    int key,siz,cnt;
    bool del;
    Node *ch[2];
    Node(){key=siz=cnt=del=0,ch[0]=ch[1]=nil;}
    Node(int x){key=x,siz=cnt=del=1,ch[0]=ch[1]=nil;}
}*root;
inline void pushup(Node *o){o->siz=o->ch[0]->siz+o->del+o->ch[1]->siz,o->cnt=o->ch[0]->cnt+1+o->ch[1]->cnt;}
inline bool isbad(Node *o){return o->ch[0]->cnt>alpha*o->cnt+5||o->ch[1]->cnt>alpha*o->cnt+5;}
void dfs(Node *o,vector<Node*> &v)
{
    if (o==nil) return;
    dfs(o->ch[0],v);
    if (o->del) v.push_back(o);
    dfs(o->ch[1],v);
    if (!o->del) delete o;
}
Node* build(vector<Node*> v,int l,int r)
{
    if (l==r) return nil;
    int mid=(l+r)>>1;
    Node *o=v[mid];
    o->ch[0]=build(v,l,mid),o->ch[1]=build(v,mid+1,r),pushup(o);
    return o;
}
vector<Node*> v;
void rebuild(Node* &o){v.clear(),dfs(o,v),o=build(v,0,v.size());}
void insert(Node* &o,int x)
{
    if (o==nil) return o=new Node(x),void();
    else
    {
        o->siz++,o->cnt++;
        if (x<=o->key) insert(o->ch[0],x);
        else insert(o->ch[1],x);
        if (isbad(o)) rebuild(o);
    }
}
int rnk(Node *o,int x)
{
    int ans=1;
    while (o!=nil)
        if (x<=o->key) o=o->ch[0];
        else ans+=o->ch[0]->siz+o->del,o=o->ch[1];
    return ans;
}
int kth(Node *o,int k)
{
    while (o!=nil)
        if (k<=o->ch[0]->siz) o=o->ch[0];
        else if (k>o->ch[0]->siz+o->del) k-=o->ch[0]->siz+o->del,o=o->ch[1];
        else return o->key;
}
void erase(Node *o,int rk)
{
    if (o->del&&rk==o->ch[0]->siz+1)
        return o->del=0,o->siz--,void();
    o->siz--;
    if (rk<=o->ch[0]->siz+o->del) erase(o->ch[0],rk);
    else erase(o->ch[1],rk-o->ch[0]->siz-o->del);
}
int main()
{
    root=nil=new Node();
    n=getint();
    int opt,x;
    while (n--)
    {
        opt=getint(),x=getint();
        if (opt==1) insert(root,x);
        if (opt==2) erase(root,rnk(root,x));
        if (opt==3) printf("%d\n",rnk(root,x));
        if (opt==4) printf("%d\n",kth(root,x));
        if (opt==5) printf("%d\n",kth(root,rnk(root,x)-1));
        if (opt==6) printf("%d\n",kth(root,rnk(root,x+1)));
    }
    return 0;
}

大佬和蒟蒻请都回答一下吧。。。

@Doubleen 2019-02-11 22:58 回复

应该是卡无点导致root为神奇的东东而无限循环吧?

@Doubleen 2019-02-11 22:59 回复

因为我写splay时是因为没add INF 和 -INF就T了这个点

@zhyyng 2019-02-11 23:06 回复

@Doubleen 修改后的代码在这里

#include<cstdio>
#include<cctype>
#include<vector>
using namespace std;
inline int getint()
{
    register int r=0,f=1;
    register char c=getchar();
    while (!isdigit(c))
        f=c=='-'?-f:f,c=getchar();
    while (isdigit(c))
        r=(r<<3)+(r<<1)+(c^48),c=getchar();
    return r*f;
}
const int N=1e5+10,INF=0x7fffffff;
const double alpha=0.75;
int n;
struct Node;
Node *nil;
struct Node
{
    int key,siz,cnt;
    bool del;
    Node *ch[2];
    Node(){key=siz=cnt=del=0,ch[0]=ch[1]=nil;}
    Node(int x){key=x,siz=cnt=del=1,ch[0]=ch[1]=nil;}
}*root;
inline void pushup(Node *o){o->siz=o->ch[0]->siz+o->del+o->ch[1]->siz,o->cnt=o->ch[0]->cnt+1+o->ch[1]->cnt;}
inline bool isbad(Node *o){return o->ch[0]->cnt>alpha*o->cnt+5||o->ch[1]->cnt>alpha*o->cnt+5;}
void dfs(Node *o,vector<Node*> &v)
{
    if (o==nil) return;
    dfs(o->ch[0],v);
    if (o->del) v.push_back(o);
    dfs(o->ch[1],v);
    if (!o->del) delete o;
}
Node* build(vector<Node*> v,int l,int r)
{
    if (l==r) return nil;
    int mid=(l+r)>>1;
    Node *o=v[mid];
    o->ch[0]=build(v,l,mid),o->ch[1]=build(v,mid+1,r),pushup(o);
    return o;
}
vector<Node*> v;
void rebuild(Node* &o){v.clear(),dfs(o,v),o=build(v,0,v.size());}
void insert(Node* &o,int x)
{
    if (o==nil) return o=new Node(x),void();
    else
    {
        o->siz++,o->cnt++;
        if (x<=o->key) insert(o->ch[0],x);
        else insert(o->ch[1],x);
        if (isbad(o)) rebuild(o);
    }
}
int rnk(Node *o,int x)
{
    int ans=1;
    while (o!=nil)
        if (x<=o->key) o=o->ch[0];
        else ans+=o->ch[0]->siz+o->del,o=o->ch[1];
    return ans;
}
int kth(Node *o,int k)
{
    while (o!=nil)
        if (k<=o->ch[0]->siz) o=o->ch[0];
        else if (k>o->ch[0]->siz+o->del) k-=o->ch[0]->siz+o->del,o=o->ch[1];
        else return o->key;
}
void erase(Node *o,int rk)
{
    if (o->del&&rk==o->ch[0]->siz+1)
        return o->del=0,o->siz--,void();
    o->siz--;
    if (rk<=o->ch[0]->siz+o->del) erase(o->ch[0],rk);
    else erase(o->ch[1],rk-o->ch[0]->siz-o->del);
}
int main()
{
    root=nil=new Node(),insert(root,-INF),insert(root,INF);
    n=getint();
    int opt,x;
    while (n--)
    {
        opt=getint(),x=getint();
        if (opt==1) insert(root,x);
        if (opt==2) erase(root,rnk(root,x));
        if (opt==3) printf("%d\n",rnk(root,x)-1);
        if (opt==4) printf("%d\n",kth(root,x+1));
        if (opt==5) printf("%d\n",kth(root,rnk(root,x)-1));
        if (opt==6) printf("%d\n",kth(root,rnk(root,x+1)));
    }
    return 0;
}
@zhyyng 2019-02-11 23:08 回复

我自己看了一下,最后一组数据好像是单调递增的。

难道现在的替罪羊树都会被用来卡二叉查找树和单旋splay的数据卡掉吗?

@zhyyng 2019-02-11 23:13 回复

还是说我有什么鸡血优化没有加?