FhqTreap各种操作模板大赏

发表于 更新于 分类于

$\ \ \ \ \ \ \ \,$关于Splay操作的复习笔记：

$\ \ \ \ \ \ \ \,$一些平衡树操作和都是一样的，详见【Splay各种操作模板大赏】。

结构

1
2
3
4
5
6
7
8
struct fhq_Treap{
	#define lson ls[rt]
	#define rson rs[rt]
  	int size[N],key[N],sum[N],val[N];
  	int ls[N],rs[N],cnt;
  	int root;
  	bool lazy[N];
}
  1. $\tt root$ ：根；
  2. $\tt cnt$ ：下标大小；
  3. $\tt key[]$ ：关键值；
  4. $\tt ls[]\&rs[]$ ：左右儿子；
  5. $\tt sum[]$ ：子树权值；
  6. $\tt val[]$ ：节点权值；
  7. $\tt size[]$ ：节点大小；
  8. $\tt lazy[]$ ：下传标记。

基本操作

  • 手写随机($Rand$)
    1
    2
    3
    4
    int Rand(){
        static int seed=233;
        return seed=int(seed*48271LL%20020207);
    }
  • 标记上传 ($pushup$)
    1
    2
    3
    4
    void pushup(int rt){
    	size[rt]=size[lson]+size[rson]+1;
    	sum[rt]=sum[lson]+sum[rson]+val[rt];
    }
  • 标记下传 ($pushdown$)，根据情况会不一样
    1
    2
    3
    4
    5
    6
    void pushdown(int rt){
      	if(!lazy[rt])return;
        swap(lson,rson);
        lazy[lson]^=1;lazy[rson]^=1;
        lazy[rt]=0;
    }
  • 分裂($split$)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //权值
    void split(int rt,int x,int &a,int &b){
        if(!rt) a=0,b=0;
        else{
        	pushdown(rt);
          	if(val[rt]<=x)a=rt,split(rson,x,rs[a],b);
          	else b=rt,split(lson,x,a,ls[b]);
          	pushup(rt);
        }
    }
    //位置
    void split(int rt,int x,int &a,int &b){
        if(!rt) a=0,b=0;
        else{
        	pushdown(rt);
        	if(size[ls[rt]]<x)a=rt,split(rson,x-size[ls[rt]]-1,rs[a],b);
          	else b=rt,split(lson,x,a,ls[b]);
          	pushup(rt);
        }
    }
  • 合并($merge$)
    1
    2
    3
    4
    5
    int merge(int x,int y){
        if(!x||!y) return x+y;
        if(key[x]<key[y]){pushdown(x);rs[x]=merge(rs[x],y);pushup(x);return x;}
        else {pushdown(y);ls[y]=merge(x,ls[y]);pushup(y);return y;}
    }

修改

  • 新建节点 ($newnode$)
    1
    2
    3
    4
    int newnode(int v){
      	sum[++cnt]=val[cnt]=v;size[cnt]=1;key[cnt]=Rand();
      	return cnt;
    }
  • 插入($Insert$)
    1
    2
    3
    4
    5
    6
    void Insert(int x,int v){
        int a,b;
        split(root,x,a,b);
        int rt=newnode(v);
        root=merge(merge(a,rt),b);
    }
  • 删除($Delete$)
    1
    2
    3
    4
    5
    6
    void Delete(int x){
        int a,b,c;
        split(root,x,a,b);split(a,x-1,a,c);
        c=merge(ls[c],rs[c]);
        root=merge(merge(a,c),b);
    }
  • 区间修改（翻转）($revse$)
    1
    2
    3
    4
    5
    6
    7
    void Reverse(int l,int r){
        int x,y,z;
        split(root,r,x,z);
        split(x,l-1,x,y);
        lazy[y]^=1;
        root=merge(merge(x,y),z);
    }

询问

  • 查找排名第k的值($QueryRank$)

    1
    2
    3
    4
    5
    6
    7
    8
    int QueryRank(int x){
        int rt=root;
        while(rt){
          	if(x==size[lson]+1)return val[rt];
          	if(size[lson]>=x)rt=lson;
          	else x-=size[lson]+1,rt=rson;
        }
    }

  • 查找某个值的排名($Rank$)

    1
    2
    3
    4
    5
    6
    7
    8
    int Rank(int x){
        int rt=root,res=1;
        while(rt){
        	if(val[rt]>=x)rt=lson;
        	else res+=size[lson]+1,rt=rson;
      	}
      	return res;
    }
  • 前驱($Numpre$)
    1
    int Numpre(int x){return QueryRank(Rank(x)-1);}
  • 后继($Numnex$)
    1
    int Numnex(int x){return QueryRank(Rank(x+1));}
  • 区间查询（权值和）($Numnex$)
    1
    2
    3
    4
    5
    6
    7
    8
    long long Query(int l,int r){
        int x,y,z;
        split(root,r,x,z);
        split(x,l-1,x,y);
        long long ans=sum[y];
        root=merge(merge(x,y),z);
        return ans;
    }

两个模板题：

  • P3369 【模板】普通平衡树
    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
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    // luogu-judger-enable-o2
    #include<algorithm>
    #include<iostream>
    #include<cstdlib>
    #include<cstring>
    #include<cctype>
    #include<cstdio>
    #include<vector>
    #include<string>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<set>
    using namespace std;
    const int inf=0x7fffffff;
    const double eps=1e-10;
    const double pi=acos(-1.0);
    //char buf[1<<15],*S=buf,*T=buf;
    //char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
    inline int read(){
        int x=0,f=1;char ch;ch=getchar();
        while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
        if(f)return x;else return -x;
    }
    const int N=1e5+10;
    struct fhq_Treap{
        #define lson ls[rt]
        #define rson rs[rt]
      int Rand(){
        static int seed=233;
        return seed=int(seed*48271LL%20020207);
      }
      int size[N],key[N],val[N];
      int ls[N],rs[N],cnt,sum[N];
      int root;
      bool lazy[N];
      void pushup(int rt){
            size[rt]=size[lson]+size[rson]+1;
            sum[rt]=sum[lson]+sum[rson]+val[rt];
        }
      int clone(int b){
      	++cnt;
        size[cnt]=size[b];key[cnt]=key[b];val[cnt]=val[b];
        ls[cnt]=ls[b];rs[cnt]=rs[b],lazy[cnt]=lazy[b];sum[cnt]=sum[b];
        return cnt;
      }
      void pushdown(int rt) {
        if(!lazy[rt])return;
        swap(lson,rson);
        lazy[lson]^=1;lazy[rson]^=1;
        lazy[rt]=0;
      }
      int merge(int x,int y){
        if(!x||!y) return x+y;
        if(key[x]<key[y]){pushdown(x);rs[x]=merge(rs[x],y);pushup(x);return x;}
        else {pushdown(y);ls[y]=merge(x,ls[y]);pushup(y);return y;}
      }
      //权值
      void split(int rt,int x,int &a,int &b){
        if(!rt) a=0,b=0;
        else{
        	pushdown(rt);
          if(val[rt]<=x)a=rt,split(rson,x,rs[a],b);
          else b=rt,split(lson,x,a,ls[b]);
          pushup(rt);
        }
      }
      void Insert(int x){
        int a,b;
        split(root,x,a,b);
        val[++cnt]=x;size[cnt]=1;key[cnt]=Rand();
        root=merge(merge(a,cnt),b);
      }
      void Delete(int x){
        int a,b,c;
        split(root,x,a,b);split(a,x-1,a,c);
        c=merge(ls[c],rs[c]);
        root=merge(merge(a,c),b);
      }
      int Rank(int x){
        int rt=root,res=1;
        while(rt){
        	if(val[rt]>=x)rt=lson;
        	else res+=size[lson]+1,rt=rson;
      	}
      	return res;
      }
      int QueryRank(int x){
        int rt=root;
        while(rt){
          if(x==size[lson]+1)return val[rt];
          if(size[lson]>=x)rt=lson;
          else x-=size[lson]+1,rt=rson;
        }
      }
      int Numpre(int x){return QueryRank(Rank(x)-1);}
      int Numnex(int x){return QueryRank(Rank(x+1));}
      void Reverse(int l,int r){
        int x,y,z;
        split(root,r,x,z);
        split(x,l-1,x,y);
        lazy[y]^=1;
        root=merge(merge(x,y),z);
      }
      long long Query(int l,int r){
        int x,y,z;
        split(root,r,x,z);
        split(x,l-1,x,y);
        long long ans=sum[y];
        root=merge(merge(x,y),z);
        return ans;
      }
    }Fhq;

    int main()
    {
      int n=read();
      while(n--){
        int opt=read(),x=read();
        if(opt==1){Fhq.Insert(x);continue;}
        if(opt==2){Fhq.Delete(x);continue;}
        if(opt==3){printf("%d\n",Fhq.Rank(x));continue;}
        if(opt==4){printf("%d\n",Fhq.QueryRank(x));continue;}
        if(opt==5){printf("%d\n",Fhq.Numpre(x));continue;}
        if(opt==6){printf("%d\n",Fhq.Numnex(x));continue;}
      }
      return 0;
    }
  • P3391 【模板】文艺平衡树（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
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    #include<algorithm>
    #include<iostream>
    #include<cstdlib>
    #include<cstring>
    #include<cctype>
    #include<cstdio>
    #include<vector>
    #include<string>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<map>
    #include<set>
    using namespace std;
    const int inf=0x7fffffff;
    const double eps=1e-10;
    const double pi=acos(-1.0);
    //char buf[1<<15],*S=buf,*T=buf;
    //char getch(){return S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++;}
    inline int read(){
    	int x=0,f=1;char ch;ch=getchar();
    	while(ch<'0'||ch>'9'){if(ch=='-') f=0;ch=getchar();}
    	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch&15);ch=getchar();}
    	if(f)return x;else return -x;
    }
    const int N=1e5+10;
    int a[N],n,m;
    struct fhq_Treap{
    	#define lson ls[rt]
    	#define rson rs[rt]
      int Rand(){
        static int seed=233;
        return seed=int(seed*48271LL%20020207);
      }
      int size[N],key[N],val[N],w[N];
      int ls[N],rs[N],cnt;
      int root;
      bool lazy[N];
      void pushup(int rt){
    		size[rt]=size[lson]+size[rson]+1;
    	}
      void pushdown(int rt) {
        if(!lazy[rt])return;
        swap(lson,rson);
        lazy[lson]^=1;lazy[rson]^=1;
        lazy[rt]=0;
      }
      int merge(int x,int y){
        if(!x||!y) return x+y;
        if(key[x]<key[y]){pushdown(x);rs[x]=merge(rs[x],y);pushup(x);return x;}
        else {pushdown(y);ls[y]=merge(x,ls[y]);pushup(y);return y;}
      }
      //位置
      void split(int rt,int x,int &a,int &b){
        if(!rt) a=0,b=0;
        else{
        	pushdown(rt);
        	if(size[ls[rt]]<x)a=rt,split(rson,x-size[ls[rt]]-1,rs[a],b);
          else b=rt,split(lson,x,a,ls[b]);
          pushup(rt);
        }
      }
    	void Insert(int x,int v){
        int a,b;
        split(root,x,a,b);++cnt;
        val[cnt]=v;size[cnt]=1;key[cnt]=Rand();
        root=merge(merge(a,cnt),b);
      }
      void Reverse(int l,int r){
        int x,y,z;
        split(root,r,x,z);
        split(x,l-1,x,y);
        lazy[y]^=1;
        root=merge(merge(x,y),z);
      }
    }Fhq;
    void write(int rt){
      Fhq.pushdown(rt);
      if(Fhq.lson)write(Fhq.lson);
      printf("%d ",Fhq.val[rt]);
      if(Fhq.rson)write(Fhq.rson); 
    }
    int main()
    {
      n=read();m=read();
     	for(int i=1;i<=n;i++)Fhq.Insert(i-1,i);
     	while(m--){
        int l=read(),r=read();
      	Fhq.Reverse(l,r);
      }
      write(Fhq.root);
      printf("\n");
    	return 0;
    }