题解【bzoj2733 [HNOI2012]永无乡】

Descriprition

两种操作

把两个集合并起来
求一个集合中的第 \(k\) 大（的编号）

\(n \leq 10^5\)

Solution

平衡树的板子题之一

维护两个点连不连通直接并查集

考虑怎么把两个集合合并

启发式合并！即把 siz 小的那一颗平衡树每一个点暴力地加入到另一个

这样做的复杂度？对于每一个点，每一次合并之后集合大小都至少是原来的两边，所以每一个点都只会被合并 \(\log n\) 次。所以这样做是 \(O(n \log n)\) 的。

实现上的细节问题：

我用了 fhqtreap（大法好！）。启发式合并的过程（借鉴了题解区里另外一个dalao的fhqtreap）可以这么写：

inline void M(node *&r, node *p) { // p 合并到 r 中

  if(!p) return ;

  M(r, p->ch[0]); M(r, p->ch[1]); // 递归左子树和右子树

  p->ch[0] = p->ch[1] = 0; // 把它左右子清空然后插到 r 里

  insert(r, p);

}

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, m, fa[N];

struct node {

  int d, id, siz, rnd;

  node *ch[2];

  inline void upd() {

    int ret = 1;

    if(ch[0]) ret += ch[0]->siz;

    if(ch[1]) ret += ch[1]->siz;

    siz = ret;

  }

}pool[N], *cur = pool, *root[N];

inline int find(int x) {

  return x == fa[x] ? x : fa[x] = find(fa[x]);

}

inline int siz(node *p) {

  if(p) return p->siz; return 0;

}

inline node *newnode(int d, int id) {

  node *p = cur++; p->rnd = (rand() << 15) + rand();

  p->siz = 1, p->d = d; p->id = id;

  p->ch[0] = p->ch[1] = 0;

  return p;

}

inline node *merge(node *p, node *q) {

  if(!p) return q;

  if(!q) return p;

  if(p->rnd <  q->rnd) { p->ch[1] = merge(p->ch[1], q); p->upd(); return p; }

  if(p->rnd >= q->rnd) { q->ch[0] = merge(p, q->ch[0]); q->upd(); return q; }

}

inline void split(node *r, int k, node *&p, node *&q) {

  if(!r) { p = q = 0; return ; }

  if(siz(r->ch[0]) < k) p = r, split(r->ch[1], k - siz(r->ch[0]) - 1, r->ch[1], q);

  else q = r, split(r->ch[0], k, p, r->ch[0]); r->upd();

}

inline int rk(node *r, int x) {

  if(!r) return 0;

  if(r->d >= x) return rk(r->ch[0], x);

  else return rk(r->ch[1], x) + siz(r->ch[0]) + 1;

}

inline void insert(node *&r, node *x) {

  node *p, *q; int k = rk(r, x->d);

  split(r, k, p, q);

  r = merge(merge(p, x), q);

}

inline void M(node *&r, node *p) { // p -> r

  if(!p) return ;

  M(r, p->ch[0]); M(r, p->ch[1]);

  p->ch[0] = p->ch[1] = 0; p->upd(); insert(r, p);

}

inline node *Merge(node *p, node *q) {

  if(p->siz <= q->siz) swap(p, q); M(p, q); return p;

}

/*

inline void out(node *p) {

  if(p->ch[0]) out(p->ch[0]);

  printf("%d ", p->d);

  if(p->ch[1]) out(p->ch[1]);

}

*/

int main() {

  scanf("%d %d", &n, &m);

  for(int i = 1; i <= n; i++) fa[i] = i;

  for(int i = 1; i <= n; i++) {

    int x; scanf("%d", &x);

    root[i] = newnode(x, i);

  } int q;

 for(int i = 1; i <= m; i++) {

    int u, v; scanf("%d %d", &u, &v);

    int fu = find(u), fv = find(v);

    if(fu == fv) continue ;

    root[fu] = Merge(root[fu], root[fv]);

    fa[fv] = fu;

  }

  scanf("%d", &q);

  for(int i = 1; i <= q; i++) {

    char op[5]; int x, y;

    scanf("%s %d %d", op, &x, &y);

    if(op[0] == 'B') {

      int fx = find(x), fy = find(y);

      if(fx == fy) continue ;

      root[fx] = Merge(root[fx], root[fy]);

      fa[fy] = fx;

    } else {

      int fx = find(x);

      node *p, *q, *r;

      if(siz(root[fx]) < y) {

        printf("-1\n"); continue ;

      }

      split(root[fx], y - 1, p, q);

      split(q, 1, q, r);

      printf("%d\n", q->id);

      root[fx] = merge(p, merge(q, r));

    }

  }

  return 0;

}

巴特西

题解【bzoj2733 [HNOI2012]永无乡】

Descriprition

Solution

Code

最新文章

热门文章