萌新写替罪羊树（
by Uichiha_Itachi @ 2019-02-11 22:51:51
能不能不要在意这种细节。。。@[Uichiha_Itachi](/space/show?uid=91016)
另外能告诉我卡的是什么吗？
by zhyyng @ 2019-02-11 22:52:52
蒟蒻求救
by zhyyng @ 2019-02-11 22:55:35
应该是卡无点导致root为神奇的东东而无限循环吧？
by Doubleen @ 2019-02-11 22:58:47
因为我写splay时是因为没add INF 和 -INF就T了这个点
by Doubleen @ 2019-02-11 22:59:34
谢谢，待会回去试一下 @[Doubleen](/space/show?uid=56432)
by zhyyng @ 2019-02-11 23:01:03
@[Doubleen](/space/show?uid=56432) 抱歉，还是T了
by zhyyng @ 2019-02-11 23:04:50
@[Doubleen](/space/show?uid=56432) 修改后的代码在这里
```cpp
#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;
}
```
by zhyyng @ 2019-02-11 23:06:43
我自己看了一下，最后一组数据好像是单调递增的。
难道现在的替罪羊树都会被用来卡二叉查找树和单旋splay的数据卡掉吗？
by zhyyng @ 2019-02-11 23:08:12
还是说我有什么鸡血优化没有加？
by zhyyng @ 2019-02-11 23:13:13