splay

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 === 版本一 === 
{{{
#include <cstdio>
#include <iostream>
#define debug(x) cout<<#x<<" = "<<x<<endl
#define KEY (bt->o[0]->o[1])
using namespace std;
typedef long long LL;
const int maxn=100001+2;

//要在最前面和最后面分别插入空节点，以方便后续操作
//区间操作时要先splay左端点，再splay右端点，然后直接对KEY进行操作就行了
struct bst{
    bst *o[2],*f;
    bool root;
    int size;
    LL w,sum,mark;
}tnull,*null=&tnull,tbt[maxn]; int tpo;
bst *bt;
bst *newnode();
void update(bst *t);
void pushdown(bst *t,int d);
void pushdown(bst *t);
void rot(bst *t);
void splay(bst *t)//还要改改...
{
    while (!t->root) rot(t);
    update(t);
    bt=t;
}
bst *find(int k)
{
    bst *t=bt;
    while (t->o[0]->size+1!=k)
    {
        if (k>t->size) return 0;
        if (k<=t->o[0]->size) t=t->o[0];
        else k-=t->o[0]->size+1,t=t->o[1];
    }
    return t;
}


bst *newnode()
{
    bst *p=&tbt[tpo++];
    p->o[0]=p->o[1]=p->f=null;
    p->root=0;
    p->size=1;
    p->w=p->sum=0;
    return p;
}
void update(bst *t)
{
    t->size=t->o[0]->size+t->o[1]->size+1;
    t->sum=t->o[0]->sum+t->o[1]->sum+t->w;
}
void pushdown(bst *t,int d)
{
    t->o[d]->sum+=t->mark*t->o[d]->size;
    t->o[d]->w+=t->mark;
    t->o[d]->mark+=t->mark;
}
void pushdown(bst *t)
{
    if (!t->mark) return;
    if (t->o[0]!=null) pushdown(t,0);
    if (t->o[1]!=null) pushdown(t,1);
    t->mark=0;
}
void rot(bst *t)
{
    bst *p=t->f;
    int d=(p->o[0]!=t);
    pushdown(p); pushdown(t);
    p->o[d]=t->o[!d]; t->o[!d]->f=p;
    t->f=p->f;
    if (p->f!=null)
        if (p->f->o[0]==p) p->f->o[0]=t;
        else               p->f->o[1]=t;
    p->f=t; t->o[!d]=p;
    t->root=p->root; p->root=0;
    update(p);
}
}}}

版本一

#include <cstdio>
#include <iostream>
#define debug(x) cout<<#x<<" = "<<x<<endl
#define KEY (bt->o[0]->o[1])
using namespace std;
typedef long long LL;
const int maxn=100001+2;
//要在最前面和最后面分别插入空节点，以方便后续操作
//区间操作时要先splay左端点，再splay右端点，然后直接对KEY进行操作就行了
struct bst{
    bst *o[2],*f;
    bool root;
    int size;
    LL w,sum,mark;
}tnull,*null=&tnull,tbt[maxn]; int tpo;
bst *bt;
bst *newnode();
void update(bst *t);
void pushdown(bst *t,int d);
void pushdown(bst *t);
void rot(bst *t);
void splay(bst *t)//还要改改...
{
    while (!t->root) rot(t);
    update(t);
    bt=t;
}
bst *find(int k)
{
    bst *t=bt;
    while (t->o[0]->size+1!=k)
    {
        if (k>t->size) return 0;
        if (k<=t->o[0]->size) t=t->o[0];
        else k-=t->o[0]->size+1,t=t->o[1];
    }
    return t;
}
bst *newnode()
{
    bst *p=&tbt[tpo++];
    p->o[0]=p->o[1]=p->f=null;
    p->root=0;
    p->size=1;
    p->w=p->sum=0;
    return p;
}
void update(bst *t)
{
    t->size=t->o[0]->size+t->o[1]->size+1;
    t->sum=t->o[0]->sum+t->o[1]->sum+t->w;
}
void pushdown(bst *t,int d)
{
    t->o[d]->sum+=t->mark*t->o[d]->size;
    t->o[d]->w+=t->mark;
    t->o[d]->mark+=t->mark;
}
void pushdown(bst *t)
{
    if (!t->mark) return;
    if (t->o[0]!=null) pushdown(t,0);
    if (t->o[1]!=null) pushdown(t,1);
    t->mark=0;
}
void rot(bst *t)
{
    bst *p=t->f;
    int d=(p->o[0]!=t);
    pushdown(p); pushdown(t);
    p->o[d]=t->o[!d]; t->o[!d]->f=p;
    t->f=p->f;
    if (p->f!=null)
        if (p->f->o[0]==p) p->f->o[0]=t;
        else               p->f->o[1]=t;
    p->f=t; t->o[!d]=p;
    t->root=p->root; p->root=0;
    update(p);
}