P3391 【模板】文艺平衡树

Lumos壹玖贰壹 · 2020-11-14 08:39:54 · 题解

FHQ_treap(码量小超好理解)

修改了一些错别字，管理员求通过

如果不会用FHQ做P3369的请左转

前言：总感觉这么做没有那么强平衡树的感觉(我太菜了)，因为作为权值的pos并没有在程序中直接体现，但好好想想也可以理解以size为比较方案的Split。因此会以此比较方案及其原因作为重点

注意： 与P3369普通平衡树的区别

Split理解

void split(int now,int &a,int &b,int k){
    if(now==0){a=0;b=0;return;}
    pushdown(now);
    if(si[t[now][0]]<k){
        a=now;
        split(t[now][1],t[now][1],b,k-si[t[now][0]]-1);
    }
    else{
        b=now;
        split(t[now][0],a,t[now][0],k);
    }
    pushup(now);
}

感觉怪怪的？

• 我们以该点对应的数在序列中的位置为权值建树。

• 但如果真用一个权值表示位置，然后像p3369中一样判断，每次翻转最多会有n个树节点的权值发生变化。而且很难优化，考虑换种方法。

• 假设我们已经按位置建了一棵树，那么点now对应的数在序列中的位置应该是size[l_son]+1。因为左子树的权值全都小于它(因为值是位置，故值都不相同)。

• 每次翻转，就在翻转区间对应子树(单独裂开成一个子树)的根打一个标记，然后只有在Split或Merge该点时将标记下传。因为翻转后左子树的权值都会比根大，右子树都会比根小，故把左右儿子换一下(左儿子指针指向右儿子，右儿子指针指向左儿子)。回溯时再统计现在的size完成更新即可\ 还不理解画个树翻一下吧

最后，因为是以pos为权值(虽然未直接体现)的平衡树，且v[]表示该节点对应序列中的值，直接从root中序遍历输出v即可

各数组意义

• v[ ]：该点对应序列中数的值
• key[ ]:类似treap用来维护平衡的关键字
• t[ ][ ]:节点的左右儿子。左:0 右:1
• f[ ]:翻转标记数组。0表示不翻，1表示翻
• si[ ]:子树大小

  各函数代码

• new_node

  inline int new_node(int x){
  v[++cnt]=x; key[cnt]=rand(); si[cnt]=1; f[cnt]=0;
  return cnt;
  }

• pushdown

  inline void pushdown(int x){
  if(f[x]){
      swap(t[x][0],t[x][1]); f[t[x][0]]^=1; f[t[x][1]]^=1; f[x]^=1;
  }
  }

• pushup

  inline void pushup(int x){
  si[x]=si[t[x][0]]+si[t[x][1]]+1;
  }

• Split

  void split(int now,int &a,int &b,int k){
  if(now==0){a=0;b=0;return;}
  pushdown(now);
  if(si[t[now][0]]<k){
      a=now;
      split(t[now][1],t[now][1],b,k-si[t[now][0]]-1);
  }
  else{
      b=now;
      split(t[now][0],a,t[now][0],k);
  }
  pushup(now);
  }

• Merge

  int merge(int a,int b){
  if(!a||!b) return a+b;
  if(key[a]<=key[b]){
      pushdown(a);
      t[a][1]=merge(t[a][1],b);
      pushup(a);
      return a;
  }
  else{
      pushdown(b);
      t[b][0]=merge(a,t[b][0]);
      pushup(b);
      return b;
  }
  }

• out

  void out(int now){
  pushdown(now);
  if(t[now][0]) out(t[now][0]);
  printf("%d ",v[now]);
  if(t[now][1]) out(t[now][1]);
  }

• main

  int main(){
  n=rd(); m=rd();
  rt=new_node(1);
  for(ri i=2;i<=n;i++) rt=merge(rt,new_node(i));
  int l,r,a,b,c;
  while(m--){
      l=rd(); r=rd();
      split(rt,a,b,l-1); split(b,b,c,r-l+1); f[b]^=1;
      rt=merge(merge(a,b),c);
  }
  out(rt);
  return 0;
  }