fhq_treap

Posted on |

本弱菜还不会$fhq-treap$，某场教做人被教做人，于是补之。

题意

给定一个序列，要求你资辞以下操作

  • 插入、删除某数
  • 区间翻转
  • 查询一个数的排名
  • 查排名为某个值的数
  • 求前驱后继
  • 区间翻转
  • 区间右移(整体右移，并且区间终点的数变为区间起点)

然后就有了$fhq-treap$

操作

$treap$每个节点有个权值，权值保持二叉搜索树结构；每个节点有个优先级，优先级保持最小堆结构。

合并两个子树

按照优先级大小合并即可，并返回合并后树的根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int merge(int x,int y)
{
    if(!x || !y) return x+y;
    pushdown(x),pushdown(y);
    if(prio[x]<prio[y]){
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);
        return y;
    }else{
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);
        return x;
    }
}

分裂成两个子树

按照特定的权值大小分裂为两个子树或者按照特定的子树大小分裂为两个子树，返回分裂后的两个子树的结点。

按权值
1
2
3
4
5
6
7
8
9
10
11
void split(int now,int k,int &x,int &y)
{
    if(!now) x=y=0;
    else{
        if(val[now]<=k)
            x=now,split(ch[now][1],k,ch[now][1],y);
        else
            y=now,split(ch[now][0],k,x,ch[now][0]);
        pushup(now);
    }
}
按大小
1
2
3
4
5
6
7
8
9
10
11
void split(int now,int k,int &x,int &y)
{
    if(!now) x=y=0;
    else{
        pushdown(now);
        if(k<=siz[ch[now][0]])
            y=now,split(ch[now][0],k,x,ch[now][0]);
        else x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
        pushup(now);
    }
}

其中$pushdown$是下传区间翻转的标记，需要时加上即可。

插入/删除一个结点

插入
1
2
3
int lef=0,rgh=0;
   split(rt,x,lef,rgh);
   rt=merge(merge(lef,newnode(x)),rgh);
删除
1
2
3
4
5
int lef=0,rgh=0,lrgh=0;
   split(rt,x,lef,rgh);
   split(lef,x-1,lef,lrgh);
   lrgh=merge(ch[lrgh][0],ch[lrgh][1]);
   rt=merge(merge(lef,lrgh),rgh);

前驱/后继

前驱
1
2
3
4
int lef=0,rgh=0;
split(rt,x-1,lef,rgh);
printf("%d\n",val[kth(lef,siz[lef])]);
rt=merge(lef,rgh);
后继
1
2
3
4
int lef=0,rgh=0;
split(rt,x,lef,rgh);
printf("%d\n",val[kth(rgh,1)]);
rt=merge(lef,rgh);

区间翻转

1
2
3
4
5
6
7
8
void getrev(int l,int r)
{
    int a=0,b=0,c=0,d=0;
    split(rt,r,a,b);
    split(a,l-1,c,d);
    rev[d]^=1;
    rt=merge(merge(c,d),b);
}

打印

1
2
3
4
5
6
7
8
void dfs(int now)
{
    if(!now) return;
    pushdown(now);
    dfs(ch[now][0]);
    if(val[now]>=1 && val[now]<=n) printf("%d ",val[now]);
    dfs(ch[now][1]);
}

排名第k大的数

1
2
3
4
5
6
7
8
int kth(int now,int k)
{
    while(1){
        if(k<=siz[ch[now][0]]) now=ch[now][0];
        else if(k==siz[ch[now][0]]+1) return now;
        else k-=siz[ch[now][0]],now=ch[now][1];
    }
}

查询一个值的排名

1
2
3
4
int lef=0,rgh=0;
split(rt,x-1,lef,rgh);
printf("%d\n",siz[lef]+1);
rt=merge(lef,rgh);

区间整体右移

1
2
3
4
5
6
int a=0,b=0,c=0,d=0;
split(rt,r,a,b);
split(a,l-1,c,d);
int lef=0,rgh=0;
split(d,r-l,lef,rgh);
rt=merge(merge(c,rgh),merge(lef,b));

模板

普通平衡树

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;
const int maxn=10*100000+5;
int prio[maxn],val[maxn],ch[maxn][2],siz[maxn];
int n,SIZ=0;
int rd=1,mo=2147483647,Base=19260817;
int getrand()
{
    rd=(rd*Base+1)&mo;
    return rd;
}
void pushup(int now){siz[now]=siz[ch[now][0]]+1+siz[ch[now][1]];}
int newnode(int valu)
{
    siz[++SIZ]=1;
    val[SIZ]=valu;
    prio[SIZ]=getrand();
    return SIZ;
}
int merge(int x,int y)
{
    if(!x || !y) return x+y;
    else{
        if(prio[x]<prio[y]){
            ch[y][0]=merge(x,ch[y][0]);
            pushup(y);
            return y;
        }else{
            ch[x][1]=merge(ch[x][1],y);
            pushup(x);
            return x;
        }
    }
}
void split(int now,int k,int &x,int &y)
{
    if(!now) x=y=0;
    else{
        if(val[now]<=k)
            x=now,split(ch[now][1],k,ch[now][1],y);
        else
            y=now,split(ch[now][0],k,x,ch[now][0]);
        pushup(now);
    }
}
int kth(int now,int k)
{
    while(1){
        if(k<=siz[ch[now][0]]) now=ch[now][0];
        else if(k==siz[ch[now][0]]+1) return now;
        else k-=siz[ch[now][0]]+1,now=ch[now][1];
    }
}
int rt=0;
void out(int now)
{
    if(!now) return;
    out(ch[now][0]);
    printf("val[%d]=%d prio[%d]=%d siz[%d]=%d\n",
        now,val[now],now,prio[now],now,siz[now]);
    out(ch[now][1]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1){
            int lef=0,rgh=0;
            split(rt,x,lef,rgh);
            rt=merge(merge(lef,newnode(x)),rgh);
        }else if(op==2){
            int lef=0,rgh=0,lrgh=0;
            split(rt,x,lef,rgh);
            split(lef,x-1,lef,lrgh);
            lrgh=merge(ch[lrgh][0],ch[lrgh][1]);
            rt=merge(merge(lef,lrgh),rgh);
        }else if(op==3){
            int lef=0,rgh=0;
            split(rt,x-1,lef,rgh);
            printf("%d\n",siz[lef]+1);
            rt=merge(lef,rgh);
        }else if(op==4){
            printf("%d\n",val[kth(rt,x)]);
        }else if(op==5){
            int lef=0,rgh=0;
            split(rt,x-1,lef,rgh);
            printf("%d\n",val[kth(lef,siz[lef])]);
            rt=merge(lef,rgh);
        }else{
            int lef=0,rgh=0;
            split(rt,x,lef,rgh);
            printf("%d\n",val[kth(rgh,1)]);
            rt=merge(lef,rgh);
        }
    }
    return 0;
}

文艺平衡树

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*100000+5;
int SIZ=0,rt=0,n,m,siz[maxn],val[maxn],prio[maxn],rev[maxn],ch[maxn][2];
int rd=1,Base=19260817,mo=2147483647;
int getrand()
{
    rd=(rd*Base+1)&mo;
    return rd;
}
int newnode(int valu)
{
    val[++SIZ]=valu;
    prio[SIZ]=getrand();
    siz[SIZ]=1;
    rev[SIZ]=0;
    return SIZ;
}
void pushup(int now){siz[now]=1+siz[ch[now][0]]+siz[ch[now][1]];}
void pushdown(int now)
{
    if(now && rev[now]){
        rev[now]=0;
        swap(ch[now][0],ch[now][1]);
        if(ch[now][0]) rev[ch[now][0]]^=1;
        if(ch[now][1]) rev[ch[now][1]]^=1;
    }
}
int merge(int x,int y)
{
    if(!x || !y) return x+y;
    pushdown(x),pushdown(y);
    if(prio[x]<prio[y]){
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);
        return y;
    }else{
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);
        return x;
    }
}
void split(int now,int k,int &x,int &y)
{
    if(!now) x=y=0;
    else{
        pushdown(now);
        if(k<=siz[ch[now][0]])
            y=now,split(ch[now][0],k,x,ch[now][0]);
        else x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
        pushup(now);
    }
}
int kth(int now,int k)
{
    while(1){
        if(k<=siz[ch[now][0]]) now=ch[now][0];
        else if(k==siz[ch[now][0]]+1) return now;
        else k-=siz[ch[now][0]],now=ch[now][1];
    }
}
int build(int l,int r)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int now=newnode(mid);
    ch[now][0]=build(l,mid-1);
    ch[now][1]=build(mid+1,r);
    pushup(now);
    return now;
}
void dfs(int now)
{
    if(!now) return;
    pushdown(now);
    dfs(ch[now][0]);
    if(val[now]>=1 && val[now]<=n) printf("%d ",val[now]);
    dfs(ch[now][1]);
}
void getrev(int l,int r)
{
    int a=0,b=0,c=0,d=0;
    split(rt,r,a,b);
    split(a,l-1,c,d);
    rev[d]^=1;
    rt=merge(merge(c,d),b);
}
int main()
{
    scanf("%d%d",&n,&m);
    rt=build(1,n);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        getrev(l,r);
    }
    dfs(rt);
    puts("");
    return 0;
}

863D Yet Another Array Queries Problem

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*100000+5;
int SIZ=0,rt=0,n,q,m,siz[maxn],val[maxn],prio[maxn],rev[maxn],ch[maxn][2],a[maxn];
int rd=1,Base=19260817,mo=2147483647;
int getrand()
{
    rd=(rd*Base+1)&mo;
    return rd;
}
int newnode(int valu)
{
    val[++SIZ]=valu;
    prio[SIZ]=getrand();
    siz[SIZ]=1;
    rev[SIZ]=0;
    return SIZ;
}
void pushup(int now){siz[now]=1+siz[ch[now][0]]+siz[ch[now][1]];}
void pushdown(int now)
{
    if(now && rev[now]){
        rev[now]=0;
        swap(ch[now][0],ch[now][1]);
        if(ch[now][0]) rev[ch[now][0]]^=1;
        if(ch[now][1]) rev[ch[now][1]]^=1;
    }
}
int merge(int x,int y)
{
    if(!x || !y) return x+y;
    pushdown(x),pushdown(y);
    if(prio[x]<prio[y]){
        ch[y][0]=merge(x,ch[y][0]);
        pushup(y);
        return y;
    }else{
        ch[x][1]=merge(ch[x][1],y);
        pushup(x);
        return x;
    }
}
void split(int now,int k,int &x,int &y)
{
    if(!now) x=y=0;
    else{
        pushdown(now);
        if(k<=siz[ch[now][0]])
            y=now,split(ch[now][0],k,x,ch[now][0]);
        else x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
        pushup(now);
    }
}
int kth(int now,int k)
{
    while(1){
        pushdown(now);
        if(k<=siz[ch[now][0]]) now=ch[now][0];
        else if(k==siz[ch[now][0]]+1) return now;
        else k-=siz[ch[now][0]]+1,now=ch[now][1];
    }
}
int build(int l,int r)
{
    if(l>r) return 0;
    int mid=(l+r)>>1;
    int now=newnode(a[mid]);
    ch[now][0]=build(l,mid-1);
    ch[now][1]=build(mid+1,r);
    pushup(now);
    return now;
}
void dfs(int now)
{
    if(!now) return;
    pushdown(now);
    dfs(ch[now][0]);
    printf("%d ",val[now]);
    dfs(ch[now][1]);
}
void getrev(int l,int r)
{
    int a=0,b=0,c=0,d=0;
    split(rt,r,a,b);
    split(a,l-1,c,d);
    rev[d]^=1;
    rt=merge(merge(c,d),b);
}
int main()
{
    scanf("%d%d%d",&n,&q,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    rt=build(1,n);
    for(int i=1;i<=q;i++){
        int typ,l,r;
        scanf("%d%d%d",&typ,&l,&r);
        if(typ==2) getrev(l,r);
        else{
            int a=0,b=0,c=0,d=0;
            split(rt,r,a,b);
            split(a,l-1,c,d);
            int lef=0,rgh=0;
            split(d,r-l,lef,rgh);
            rt=merge(merge(c,rgh),merge(lef,b));
        }
    }
    for(int i=1;i<=m;i++){
        int b;
        scanf("%d",&b);
        printf("%d\n",val[kth(rt,b)]);
    }
    return 0;
}