P3391

发表于 更新于 分类于
【模板】文艺平衡树

【模板】文艺平衡树

一、Splay

就是 Splay 区间翻转模板。

我们采取这样的策略，多塞一个极小点和一个极大点。

每次翻转 $[l,r]$ 的时候，先找到 $l-1$ 和 $r+1$，将 $l-1$ 转到根，$r+1$ 转到 $l-1$ 下方，然后要翻转的区间就是 $r+1$ 的左子树，打上标记即可。（以上的 $l-1$ 指的是在区间中排在第 $l-1$ 个位置上的数对应 Splay 中的点）

因为有了懒标记，所以要记得下传（这当然是废话）。

时间复杂度 $O(n\log n)$。

关于 Splay 上的懒标记下传。这里使用的懒标记下传区别于线段树的懒标记下传，我们这个标记的意思是“当前这个点尚未修改，但是已经有修改操作发出了”。（当然你也可以理解为这个东西和 Splay 的区间翻转这个性质有关，所以和线段树下传的标记表示的意思是一样的）

下传啥的因为一般从根开始在 Splay 上操作所以及时下传肯定是没有问题的，不会出现什么转着转着把标记转散了这种事情。

当然也有特例，比如说 LCT 上的一些操作（可能会从某个非根节点开始），这个时候就需要特别在 splay 函数中特别加入一个从根开始逐个 Pushdown 的 Update 函数。

代码（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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,m,l,r;

ll buffa[N+5],bufch0[N+5],bufch1[N+5],bufval[N+5],bufcnt[N+5],bufsiz[N+5];
bool buftag[N+5];
ll *nowfa=buffa,*nowch0=bufch0,*nowch1=bufch1,*nowval=bufval,
  *nowcnt=bufcnt,*nowsiz=bufsiz;
bool *nowtag=buftag;

inline ll read() {
  ll ret=0,f=1;char ch=getchar();
  while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
  while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
  return ret*f;
}

inline void write(ll x) {
  static char buf[22];static ll len=-1;
  if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
  else {putchar('-');do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
  while(len>=0) putchar(buf[len--]);
}

struct Splay{
  ll *fa,*ch[2],*val,*cnt,*siz;
  bool *tag;
  ll rt,sz;
  inline void Init(ll x) {
    fa=nowfa;ch[0]=nowch0;ch[1]=nowch1;
    val=nowval;cnt=nowcnt;siz=nowsiz;tag=nowtag;
    nowfa+=x+1;nowch0+=x+1;nowch1+=x+1;
    nowval+=x+1;nowcnt+=x+1;nowsiz+=x+1;nowtag+=x+1;
  }
  inline void Pushup(ll x) {siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+cnt[x];}
  inline void Pushdown(ll x) {
    if(x&&tag[x]) {
      tag[ch[0][x]]^=1;tag[ch[1][x]]^=1;swap(ch[0][x],ch[1][x]);tag[x]=0;
    }
  }
  inline bool Get(ll x) {return x==ch[1][fa[x]];}
  inline void Rotate(ll x) {
    ll y=fa[x],z=fa[y],c=Get(x);ch[c][y]=ch[c^1][x];
    if(ch[c^1][x]) fa[ch[c^1][x]]=y;ch[c^1][x]=y;fa[y]=x;fa[x]=z;
    if(z) ch[y==ch[1][z]][z]=x;Pushup(y);Pushup(x);
  }
  inline void splay(ll x,ll g) {
    for(ll f=fa[x];(f=fa[x])!=g;Rotate(x)) {
      if(fa[f]!=g) Rotate(Get(f)==Get(x)?f:x);
    }
    if(g==0) rt=x;
  }
  inline void Ins(ll k) {
    if(!rt) {
      val[++sz]=k;cnt[sz]++;rt=sz;Pushup(rt);return;
    }
    ll cur=rt,f=0;
    while(1) {
      Pushdown(cur);
      if(val[cur]==k) {
        cnt[cur]++;Pushup(cur);Pushup(f);splay(cur,0);break;
      }
      f=cur;cur=ch[k>val[cur]][cur];
      if(!cur) {
        val[++sz]=k;cnt[sz]++;fa[sz]=f;ch[k>val[f]][f]=sz;
        Pushup(sz);Pushup(f);splay(sz,0);break;
      }
    }
  }
  inline ll Kth(ll x) {
    ll cur=rt;
    while(1) {
      Pushdown(cur);
      if(ch[0][cur]&&x<=siz[ch[0][cur]]) {cur=ch[0][cur];}
      else {
        x-=cnt[cur]+siz[ch[0][cur]];
        if(x<=0) return splay(cur,0),cur;cur=ch[1][cur];
      }
    }
  }
  inline void Print(ll x) {
    Pushdown(x);
    if(ch[0][x]) Print(ch[0][x]);
    if(val[x]>=1&&val[x]<=n) {write(val[x]);putchar(' ');}
    if(ch[1][x]) Print(ch[1][x]);
  }
}s;

int main() {
  
  n=read();m=read();

  s.Init(n+3);

  for(ll i=0;i<=n+1;i++) s.Ins(i);

  while(m--) {
    l=read();r=read();
    ll tmpl=s.Kth(l),tmpr=s.Kth(r+2);
    s.splay(tmpl,0);s.splay(tmpr,tmpl);
    s.tag[s.ch[0][tmpr]]^=1;
  }
  
  s.Print(s.rt);
  
  return 0;
}

二、FHQ-Treap

分裂合并什么的肯定是要及时下传的。

剩下感觉没什么区别啊，不过就是依靠子树大小分裂排名而已。

代码（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
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;
inline void writes(ll x) {write(x);putchar(32);}

const ll N=1e5;

ll bufch[2][N+5],bufval[N+5],bufsiz[N+5],bufrnd[N+5],bufrev[N+5];
ll *nowch[2]={bufch[0],bufch[1]},*nowval=bufval,*nowsiz=bufsiz
  ,*nowrnd=bufrnd,*nowrev=bufrev;

struct Fhq_Treap{
  ll *ch[2],*val,*siz,*rnd,*rev;ll rt,sz;
  inline void Init(ll x) {
    x+=3;ch[0]=nowch[0];ch[1]=nowch[1];val=nowval;siz=nowsiz;
    rnd=nowrnd;rev=nowrev;
    nowch[0]+=x;nowch[1]+=x;nowval+=x;nowsiz+=x;nowrnd+=x;nowrev+=x;
  }
  inline void Pushup(ll x) {siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+1;}
  inline void Pushdown(ll x) {
    if(rev[x]) {
      swap(ch[0][x],ch[1][x]);rev[x]=0;
      if(ch[0][x]) rev[ch[0][x]]^=1;if(ch[1][x]) rev[ch[1][x]]^=1;
    }
  }
  inline void Split_(ll p,ll k,ll &x,ll &y) {
    if(!p) {x=y=0;return;}Pushdown(p);
    if(siz[ch[0][p]]<k) {x=p;Split_(ch[1][x],k-siz[ch[0][p]]-1,ch[1][x],y);}
    else {y=p;Split_(ch[0][y],k,x,ch[0][y]);}Pushup(p);
  }
  inline ll Merge(ll x,ll y) {
    if(!x||!y) return x|y;
    if(rnd[x]<rnd[y]) {
      Pushdown(y);ch[0][y]=Merge(x,ch[0][y]);Pushup(y);return y;
    }
    else {
      Pushdown(x);ch[1][x]=Merge(ch[1][x],y);Pushup(x);return x;
    }
  }
  inline void Ins(ll k) {
    val[++sz]=k;siz[sz]++;rnd[sz]=rand();
    if(!rt) {rt=sz;return;}rt=Merge(rt,sz);
  }
  inline void Rev(ll l,ll r) {
    ll x,y,z;Split_(rt,l-1,x,y);Split_(y,r-l+1,y,z);
    rev[y]^=1;rt=Merge(x,Merge(y,z));
  }
  inline void Print(ll p) {
    if(!p) return;
    Pushdown(p);Print(ch[0][p]);writes(val[p]);Print(ch[1][p]);
  }
}t;

int main() {
  
  srand(73939133);ll n,m;n=read();m=read();t.Init(n);
  for(ll i=1;i<=n;i++) {t.Ins(i);}

  while(m--) {ll l,r;l=read();r=read();t.Rev(l,r);}

  t.Print(t.rt);

  return 0;
}