跳转至

平衡树

普通平衡树 FHQ_Treap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
namespace FHQ_Treap
{
    int lson[MAX],rson[MAX];
    int rnd[MAX],val[MAX],sum[MAX],siz[MAX];
    int root,tot;
    int stk[MAX],top;
    inline int randoom(int l=0,int r=INF)
    {
        static mt19937_64 sd(20070707);
        static uniform_int_distribution<int> range(l,r);
        return range(sd);
    }
    inline void pushup(int i)
    {
        siz[i]=siz[lson[i]]+siz[rson[i]]+1;
        sum[i]=sum[lson[i]]+sum[rson[i]]+val[i];
    }
    inline int newnode(int k)
    {
        int now=top?stk[top--]:++tot;
        rnd[now]=randoom(),val[now]=sum[now]=k,siz[now]=1,lson[now]=rson[now]=0;
        return now;
    }
    void split(int now,int k,int &l,int &r)
    {
        if(!now) return l=r=0,void();
        if(val[now]<=k) l=now,split(rson[now],k,rson[now],r);
        else r=now,split(lson[now],k,l,lson[now]);
        pushup(now);
    }
    int merge(int l,int r)
    {
        if(!l||!r) return l|r;
        if(rnd[l]<rnd[r]) return rson[l]=merge(rson[l],r),pushup(l),l;
        else return lson[r]=merge(l,lson[r]),pushup(r),r;
    }
    inline void ins(int k)
    {
        int x=0,y=0;
        split(root,k,x,y);
        root=merge(merge(x,newnode(k)),y);
    }
    inline void del(int k)
    {
        int x=0,y=0,z=0;
        split(root,k,x,z);
        split(x,k-1,x,y);
        stk[++top]=y,y=merge(lson[y],rson[y]);
        root=merge(merge(x,y),z);
    }
    inline int lis(int k)
    {
        int x=0,y=0;
        split(root,k-1,x,y);
        int ans=siz[x]+1;
        root=merge(x,y);
        return ans;
    }
    int kthand(int now,int k)
    {
        if(siz[lson[now]]+1==k) return val[now];
        else if(siz[lson[now]]>=k) return kthand(lson[now],k);
        else return kthand(rson[now],k-siz[lson[now]]-1);
    }
    inline int pre(int k)
    {
        int x=0,y=0;
        split(root,k-1,x,y);
        int ans=kthand(x,siz[x]);
        root=merge(x,y);
        return ans;
    }
    inline int suf(int k)
    {
        int x=0,y=0;
        split(root,k,x,y);
        int ans=kthand(y,1);
        root=merge(x,y);
        return ans;
    }
}

文艺平衡树 FHQ_Treap

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
namespace FHQ_Treap
{
    int lson[MAX],rson[MAX];
    int rnd[MAX],val[MAX],siz[MAX],tag[MAX];
    int root,tot;
    int stk[MAX],top;
    inline int randoom(int l=0,int r=INF)
    {
        static mt19937_64 sd(20070707);
        static uniform_int_distribution<int> range(l,r);
        return range(sd);
    }
    inline void pushup(int i)
    {
        siz[i]=siz[lson[i]]+siz[rson[i]]+1;
    }
    inline void down(int i)
    {
        if(i) tag[i]^=1,Swp(lson[i],rson[i]);
    }
    inline void pushdown(int i)
    {
        if(tag[i]) down(lson[i]),down(rson[i]),tag[i]=0;
    }
    inline int newnode(int k)
    {
        int now=top?stk[top--]:++tot;
        rnd[now]=randoom(),val[now]=k,siz[now]=1,lson[now]=rson[now]=0;
        return now;
    }
    void split(int now,int k,int &l,int &r)
    {
        if(!now) return l=r=0,void();
        pushdown(now);
        if(siz[lson[now]]+1<=k) l=now,split(rson[now],k-siz[lson[now]]-1,rson[now],r);
        else r=now,split(lson[now],k,l,lson[now]);
        pushup(now);
    }
    int merge(int l,int r)
    {
        if(!l||!r) return l|r;
        if(rnd[l]<rnd[r]) return pushdown(l),rson[l]=merge(rson[l],r),pushup(l),l;
        else return pushdown(r),lson[r]=merge(l,lson[r]),pushup(r),r;
    }
    inline void reverse(int L,int R)
    {
        int l=0,r=0,mid=0;
        split(root,R,l,r);
        split(l,L-1,l,mid);
        down(mid);
        root=merge(merge(l,mid),r);
    }
}

普通平衡树 Splay

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
namespace Splay
{
    int fa[MAX],ch[MAX][2],val[MAX],siz[MAX],cnt[MAX];
    int root,tot,stk[MAX],top;
    inline void pushup(int i) {siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+cnt[i];}
    inline void rotate(int x)
    {
        int y=fa[x],z=fa[y];
        int k1=ch[y][1]==x,k2=ch[z][1]==y;
        ch[z][k2]=x,fa[x]=z;
        ch[y][k1]=ch[x][k1^1],fa[ch[x][k1^1]]=y;
        ch[x][k1^1]=y,fa[y]=x;
        pushup(y),pushup(x);
    }
    inline void splay(int x,int goal)
    {
        while(fa[x]!=goal)
        {
            int y=fa[x],z=fa[y];
            if(z!=goal) ((ch[z][0]==y)^(ch[y][0]==x))?rotate(x):rotate(y);
            rotate(x);
        }
        if(!goal) root=x;
    }
    inline void find(int k)
    {
        int now=root;
        if(!now) return;
        while(k!=val[now]&&ch[now][val[now]<k]) now=ch[now][val[now]<k];
        splay(now,0);
    }
    inline int rnk(int k)
    {
        return find(k),siz[ch[root][0]];
    }
    inline int adjacent(int k,int flag)
    {
        find(k);
        int now=root;
        if(val[now]>k&&flag) return now;
        if(val[now]<k&&!flag) return now;
        now=ch[now][flag];
        while(ch[now][flag^1]) now=ch[now][flag^1];
        return now; 
    }
    inline void ins(int k)
    {
        int now=root,father=0;
        while(val[now]!=k&&now) father=now,now=ch[now][val[now]<k];
        if(now) ++cnt[now];
        else
        {
            now=top?stk[top--]:++tot;
            if(father) ch[father][val[father]<k]=now;
            ch[now][0]=ch[now][1]=0,val[now]=k,cnt[now]=1,siz[now]=1,fa[now]=father;
        }
        splay(now,0);
    }
    inline void del(int k)
    {
        int pre=adjacent(k,0),suf=adjacent(k,1);
        splay(pre,0),splay(suf,pre);
        int D=ch[suf][0];
        if(cnt[D]>1) --cnt[D],splay(D,0); else ch[suf][0]=0,stk[++top]=D;
    }
    inline int kthand(int k)
    {
        int now=root;
        if(siz[now]<k) return 0;
        while(1)
        {
            int lson=ch[now][0];
            if(k>siz[lson]+cnt[now]) k-=siz[lson]+cnt[now],now=ch[now][1];
            else if(k<=siz[lson]) now=ch[now][0];
            else return val[now];
        }
    }
}

文艺平衡树 Splay

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
namespace Splay
{
    int fa[MAX],ch[MAX][2],val[MAX],siz[MAX],rev[MAX];
    int root,tot,stk[MAX],top;
    inline void pushup(int i)   {siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+1;}
    inline void down(int i)     {if(i) rev[i]^=1,Swp(ch[i][0],ch[i][1]);}
    inline void pushdown(int i) {if(rev[i]) down(ch[i][0]),down(ch[i][1]),rev[i]=0;}
    inline void rotate(int x)
    {
        int y=fa[x],z=fa[y];
        int k1=ch[y][1]==x,k2=ch[z][1]==y;
        ch[z][k2]=x,fa[x]=z;
        ch[y][k1]=ch[x][k1^1],fa[ch[x][k1^1]]=y;
        ch[x][k1^1]=y,fa[y]=x;
        pushup(y),pushup(x);
    }
    inline void splay(int x,int goal)
    {
        while(fa[x]!=goal)
        {
            int y=fa[x],z=fa[y];
            if(z!=goal) ((ch[z][0]==y)^(ch[y][0]==x))?rotate(x):rotate(y);
            rotate(x);
        }
        if(!goal) root=x;
    }
    inline int kthand(int k)
    {
        int now=root;
        if(siz[now]<k) return 0;
        while(1)
        {
            pushdown(now);
            int lson=ch[now][0];
            if(k>siz[lson]+1) k-=siz[lson]+1,now=ch[now][1];
            else if(k<=siz[lson]) now=ch[now][0];
            else return val[now];
        }
    }
    inline void reverse(int L,int R)
    {
        int x=kthand(L-1),y=kthand(R+1);
        splay(x,0),splay(y,x);
        down(ch[ch[root][1]][0]);
    }
}