首页 > 其他分享 >[lnsyoj300/luoguP3224/HNOI2012]永无乡

[lnsyoj300/luoguP3224/HNOI2012]永无乡

时间:2024-07-13 18:20:55浏览次数:13  
标签:return lnsyoj300 int 合并 tr HNOI2012 luoguP3224 key size

题意

给定 \(n\) 个集合,每个集合最开始只包含数 \(a_i\),然后进行 \(m\) 次合并操作。具体地,每次操作将数 \(a_i\) 所在的集合与数 \(a_j\) 所在的集合合并。
接下来,进行 \(q\) 次操作,每次操作可能为合并操作与查询操作,合并操作与上述相同,查询操作为查询数 \(a_x\) 所在的集合中第 \(k\) 小的数的下标。

sol

这里的查询操作为根据排名查数,且需要维护集合的合并操作,因此使用并查集套平衡树。平衡树使用 FHQ-Treap,具体用法见[lnsyoj285/luoguP2596/ZJOI2006]书架
需要注意的是,虽然使用的是以分裂与合并为基本操作的 FHQ-Treap,但不能直接使用 FHQ-Treap 的合并操作来进行平衡树的合并。因为 FHQ-Treap 所合并的两棵平衡树必须内部节点的值域没有交集(按值分裂)或在序列中的位置没有交集(按排名分裂)。我们只能使用启发式合并。

启发式合并

平衡树的启发式合并非常简单,只需要将较小的那棵树的每一个节点都插入另一棵树中即可,可以递归进行处理。
代码(此处假设被插入树的元素个数大于插入树的元素个数):

void merge_tree(int &r, int u){ // r 为被插入树的根,u 为应插入的节点编号
    if (tr[u].l) merge_tree(r, tr[u].l);
    if (tr[u].r) merge_tree(r, tr[u].r);
    tr[u].l = tr[u].r = 0;
    insert(r, u);
}

查询操作为 BST(二叉搜索树)的基本操作,具体移步[lnsyoj118/luoguP3369]普通平衡树

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>

using namespace std;

const int N = 100005;

struct Node{
    int l, r;
    int key, val;
    int size;
}tr[N];

int fa[N];
int n, m, q;
int idx;
int root[N];

int find(int x){
    if (fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int create(int key){
    tr[ ++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].size = 1;
    return idx;
}

void pushup(int u){
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}

void split(int u, int key, int &x, int &y){
    if (!u) {
        x = y = 0;
        return ;
    }
    if (tr[u].key <= key) x = u, split(tr[u].r, key, tr[x].r, y);
    else y = u, split(tr[u].l, key, x, tr[y].l);
    pushup(u);
}

int merge(int x, int y){
    if (!x || !y) return x | y;
    if (tr[x].val <= tr[y].val){
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

void insert(int &r, int u){
    int r1 = 0, r2 = 0;
    split(r, tr[u].key, r1, r2);
    r = merge(r1, merge(u, r2));
}

void merge_tree(int &r, int u){
    if (tr[u].l) merge_tree(r, tr[u].l);
    if (tr[u].r) merge_tree(r, tr[u].r);
    tr[u].l = tr[u].r = 0;
    insert(r, u);
}

int get_key(int u, int rank){
    if (rank > tr[u].size) return -1;
    if (tr[tr[u].l].size >= rank) return get_key(tr[u].l, rank);
    if (tr[tr[u].l].size + 1 == rank) return u;
    return get_key(tr[u].r, rank - tr[tr[u].l].size - 1);
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ){
        int t;
        scanf("%d", &t);
        root[i] = create(t);
        fa[i] = i;
    }
    while (m -- ){
        int x, y;
        scanf("%d%d", &x, &y);
        int fx = find(x), fy = find(y);
        if (fx == fy) continue;
        if (tr[root[fx]].size < tr[root[fy]].size) swap(fx, fy);
        fa[fy] = fx;
        merge_tree(root[fx], root[fy]);
    }
    scanf("%d", &q);
    while (q -- ){
        char op[2];
        int x, y;
        scanf("%s%d%d", op, &x, &y);
        if (*op == 'B'){
            int fx = find(x), fy = find(y);
            if (fx == fy) continue;
            if (tr[root[fx]].size < tr[root[fy]].size) swap(fx, fy);
            fa[fy] = fx;
            merge_tree(root[fx], root[fy]);
        }
        else {
            int fx = find(x);
            int r = root[fx];
            printf("%d\n", get_key(r, y));
        }
    }
}

蒟蒻犯的若至错误

  • 使用并查集前没有初始化并查集
  • 启发式合并时没有清空插入节点的儿子(不影响其正确性,但会浪费空间)

标签:return,lnsyoj300,int,合并,tr,HNOI2012,luoguP3224,key,size
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/lnsyoj300_luoguP3224

相关文章

  • [HNOI2012] 矿场搭建 题解
    [HNOI2012]矿场搭建前置知识:#Tarjan求点双连通分量题目大意​ 给你一张无向连通图,任意删去其中一个点,要求在删点后在每个连通块中有一个点被选择,问至少需要选择多少个点,以及选择的方案数。输入输出格式输入​ 多组数据以\(N=0\)结束​ 每组数据第一行为边的数量\(N\(N......
  • P3219 [HNOI2012] 三角形覆盖问题&P1222 三角形 题解
    严格单$\log$做法,附实现细节和代码。考虑从左往右扫描线,发现每次操作是线段上端点$-1$,插入线段,删除退化成点的线段。如果某时刻一条线段被另一条完全覆盖,那么这条线段显然不会产生贡献,可以删去。最后得到的线段一定是左端点单调递增时,右端点也单调递增,可以用set维护。当两......
  • 【题解】HNOI2012 - 集合选数
    HNOI2012-集合选数https://www.luogu.com.cn/problem/P3226不算难的非显然状压dp。首先根据限制条件建图,\((x,2x),(x,3x)\)连边,表示边上相邻两个点不能同时选,然后一组独立集就是一个可行的集合。发现画出来的图是若干个部分网格图,每个连通块最小的点都是与\(6\)互质的数......
  • [HNOI2012] 集合选数
    [HNOI2012]集合选数目录题目描述输入格式输出格式样例#1样例输入#1样例输出#1提示题意概括思路历程:1.设计状态2.设计转移代码实现:题目描述《集合论与图论》这门课程有一道作业题,要求同学们求出\(\{1,2,3,4,5\}\)的所有满足以下条件的子集:若\(x\)在该子集中,则\(2......
  • BZOJ 2730: [HNOI2012]矿场搭建 tarjan割点
    2730:[HNOI2012]矿场搭建TimeLimit: 10Sec  MemoryLimit: 128MBSubmit: 2010  Solved: 935[Submit][Status][Discuss]Description煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见,希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口......
  • Luogu P3224 [HNOI2012]永无乡
    [HNOI2012]永无乡题目描述永无乡包含\(n\)座岛,编号从\(1\)到\(n\),每座岛都有自己的独一无二的重要度,按照重要度可以将这\(n\)座岛排名,名次用\(1\)到\(n\)来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛到达另一个岛。如果从岛\(a\)出发经过若干座(含\(0\)......
  • 题解 P3225 [HNOI2012] 矿场搭建
    解析传送门一道简单的tarjan题题意:在无向图中找一些点,这些点组成的的点集记为\(V\),使得去掉任意一个点,剩下的每一个点都可以到达\(V\)中任意一个点,求点集\(V\)的大小的最小值及其方案数。去掉一个点,很自然的联想到割点,那么考虑一下割点在不在备选集合中。如图,显然可以看出,......
  • P3224 [HNOI2012]永无乡 题解
    典型Splay练习题。开始建\(n\)个Splay,每一次建边用并查集判断是否在一个子图,不在就合并,即把一个Splay的所有点全插入到另一个Splay中,需要合并的点可以用vector存储。但......
  • P3226 [HNOI2012]集合选数
    简要题意给你一个\(n\)个元素的集合,它由前\(n\)个正整数构成。你需要求出它有多少个非空子集,满足若\(x\)在这个子集中,\(2x,3x\)不能在子集中。由于答案可能很大,你......
  • P3225 [HNOI2012]矿场搭建 tarjan
    //题意:在一幅无向图图上,删除一个点后,其他所有点上的人还能通过其他点出去,问最少设置几个出口,以及方案数//思路:无向图就联想到双联通分量,我们来分类讨论一下//1......