P3224题解

intel_core · 2020-06-18 18:22:03 · 题解

HN不愧为强省，省选题坑我一页提交.....wtcl
言归正传，这是一道FHQ Treap/线段树合并的练手好题。
分析下题目：

• 操作1：B x y表示在岛x与岛y之间修建一座新桥。
• 操作2：Q x k表示询问当前与岛x连通的所有岛中第k重要的是哪座岛，即所有与岛x连通的岛中重要度排名第k小的岛是哪座，请你输出那个岛的编号。

操作1：

• 并查集 这不需要我多讲了吧
• 将两个集合合并(①)
  操作2：
• 查询集合中第k小的数(权值线段树/Treap均可)
  ①需要将两个集合里的树合并
• FHQ Treap+启发式合并
• 权值线段树合并
  这两种方法都可以解决①
  两种方法的时间复杂度都是O(nlogn) 注意：
• 但是FHQ Treap的空间复杂度是O(n)的
• 然鹅线段树合并的空间是O(nlogn)的
  因为权值线段树空间大，所以要复用空间
  写成这样会MLE：

  int merge(int x,int y,int l,int r){
      if(!x||!y)return x+y;
      if(!id)id=++tot;
      if(l==r){
          t[id].maxa=t[x].size+t[y].size;
          return x;
      }
      int mid=(l+r)>>1;
      t[id].ch[0]=merge(t[id].ch[0],t[y].ch[0],l,mid);
      t[id].ch[1]=merge(t[id].ch[1],t[y].ch[1],mid+1,r);
      update(id);
      return id;
  }

  这样才能AC：

  int merge(int x,int y,int l,int r){
      if(!x||!y)return x+y;
      if(l==r){
          t[x].maxa+=t[y].maxa;
          return x;
      }
      int mid=(l+r)>>1;
      t[x].ch[0]=merge(t[x].ch[0],t[y].ch[0],l,mid);
      t[x].ch[1]=merge(t[x].ch[1],t[y].ch[1],mid+1,r);
      update(x);
      return x;
  }

  Treap的启发式合并，只需把Tree1里的节点一个个插到Tree2里就行。
  效果如下：

  void dfs(int id,int &target){
      if(!id)return;
      dfs(t[id].ch[0],target);
      dfs(t[id].ch[1],target);
      t[id].ch[0]=t[id].ch[1]=0;
      t[id].size=1;
      int x=t[id].val;
      int rt1,rt2;
      split(target,x,rt1,rt2);
      target=merge(rt1,merge(id,rt2));
  }

  此题并查集也有坑：
  如果直接合并两个集合，集合里所有元素相当于出现了两次。
  WA写法：

  void mergeSet(int x,int y){
      if(t[rt[x]].size>t[rt[y]].size)swap(x,y);
      fa[x]=y;
      dfs(rt[x],rt[y]);
  }

  这样才能AC：

  void mergeSet(int x,int y){
      if(check(x,y))return;
      if(t[rt[x]].size>t[rt[y]].size)swap(x,y);
      fa[x]=y;
      dfs(rt[x],rt[y]);
  }

  一定要快读
  Get到了以上技巧，你就能在800ms~1000msA掉本题
  上代码(FHQ Treap+启发式合并)

  #pragma optimize(5, "inline", "Ofast")
  #include <iostream>
  #include <algorithm>
  #include <cstdio>
  #include <cmath>
  #include <queue>
  #include <cstring>
  using namespace std;
  const int NR=1e5+10;
  int fa[NR];
  int n,m,q;
  //------FHQ Treap--------
  struct node{
    int ch[2];
    int val;
    int rnd;
    int size;
    int id;
  }t[NR];
  int tot;
  void update(int id){
          t[id].size=t[t[id].ch[0]].size+t[t[id].ch[1]].size+1;
  }
  int newNode(int val,int id){
      tot++;
      t[tot].val=val;
      t[tot].size=1;
      t[tot].rnd=rand();
      t[tot].id=id;
      return tot;
  }
  void split(int id,int val,int &x,int &y){
      if(!id){
          x=y=0;
          return;
      }
      if(val>=t[id].val){
          y=id;
          split(t[id].ch[0],val,x,t[id].ch[0]);
      }
      else{
          x=id;
          split(t[id].ch[1],val,t[id].ch[1],y);
      }
      update(id);
  }
  int merge(int x,int y){
      if(!x||!y)return x+y;
      if(t[x].rnd<t[y].rnd){
          t[x].ch[1]=merge(t[x].ch[1],y);
          update(x);
          return x;
      }
      else{
          t[y].ch[0]=merge(x,t[y].ch[0]);
          update(y);
          return y;
      }
  }
  void splitk(int id,int k,int &x,int &y){
      if(!id){
          x=y=0;
          return;
      }
      int lsize=t[t[id].ch[0]].size;
      if(k<=lsize){
          y=id;
          splitk(t[id].ch[0],k,x,t[id].ch[0]);
      }
      else{
          x=id;
          splitk(t[id].ch[1],k-lsize-1,t[id].ch[1],y);
      }
      update(id);
  }
  //-------并查集--------
  int rt[NR];
  void init(){
      for(int i=1;i<=n;i++)
          fa[i]=i;
  }
  int get(int x){
      if(fa[x]==x)
          return x;
      return fa[x]=get(fa[x]);
  }
  bool check(int &x,int &y){
      x=get(x);
      y=get(y);
      return x==y;
  }
  void dfs(int id,int &target){
      if(!id)return;
      dfs(t[id].ch[0],target);
      dfs(t[id].ch[1],target);
      t[id].ch[0]=t[id].ch[1]=0;
      t[id].size=1;
      int x=t[id].val;
      int rt1,rt2;
      split(target,x,rt1,rt2);
      target=merge(rt1,merge(id,rt2));
  }
  void mergeSet(int x,int y){
      if(check(x,y))return;
      if(t[rt[x]].size>t[rt[y]].size)swap(x,y);
      fa[x]=y;
      dfs(rt[x],rt[y]);
  }
  int main(int argc, char const *argv[])
  {
      freopen("1.in","r",stdin);
      freopen("1.out","w",stdout);
      cin>>n>>m;
      init();
      for(int i=1;i<=n;i++){
          int x;
          scanf("%d",&x);
          rt[i]=newNode(x,i);
      }
      for(int i=1;i<=m;i++){
          int u,v;
          scanf("%d%d",&u,&v);
          mergeSet(u,v);
      }
      cin>>q;
      for(int i=1;i<=q;i++){
          char opt;
          int x,y;
          scanf(" %c%d%d",&opt,&x,&y);
          if(opt=='Q'){
              x=get(x);
              if(t[rt[x]].size<y){
                  puts("-1");
                  continue;
              }
              int rt1,rt2,rt3;
              int wxb=t[rt[x]].size;
              splitk(rt[x],wxb-y,rt1,rt2);
              splitk(rt2,1,rt2,rt3);
              printf("%d\n",t[rt2].id);
              rt[x]=merge(rt1,merge(rt2,rt3));
          }
          else mergeSet(x,y);
      }
    return 0;
  }

  All in All

• 公既知天命识时务，何乃不点我关注？