精华内容
下载资源
问答
  • 启发式合并

    2018-12-30 12:49:45
    启发式合并
    #include<cstdio>
    const int N=5e5+5;
    int f[N],d[N],r[N],p[N];
    int find(int i){
        if(p[i]==i)return i;
        register int j=find(p[i]);
        d[i]=d[p[i]]+1;
        return j;
    }
    int unionn(int i,int j){
        i=find(i),j=find(j);
        if(i==j)return 0;
        if(r[i]==r[j])++r[j];
        if(r[i]<r[j]){
            p[i]=j;
            return i;
        }
        p[j]=i;
        return j;
    }
    int query(int i,int j){
        register int s=0;
        if(find(i)==find(j))
            while(i!=j)
                if(d[i]>d[j])s<f[i]?s=f[i]:0,i=p[i];
                else s<f[j]?s=f[j]:0,j=p[j];
    /************
    else下语句等价于
    if(s<f[j]) {
    s=f[j]
    };else{
    };
    i=p[i];
    **********************/
        return s;
    }
    inline void read(int &res){
        static char ch;
        while((ch=getchar())<'0'||ch>'9');res=ch-48;
        while((ch=getchar())>='0'&&ch<='9')res=res*10+ch-48;
    }
    int main(){
        register int n,m,k,s,t,last=0;
        read(n),read(m);
        for(;n;--n)p[n]=n;
        while(m--){
            read(k),read(s),read(t);
            s^=last,t^=last; //异或是题目要求
            if(k)printf("%d\n",last=query(s,t));
            else f[unionn(s,t)]=++n;
        }
    }
    并查集[按秩启发式合并]
    BZOJ4668-冷战
    【题目大意】
    给出N个军工厂和M 个操作,操作分为两类:
    •0 u v,这次操作苏联会修建一条连接u号军工厂及v号军工厂的铁路,注意铁路都是双向
    •1 u v,Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通,假如到这次操作都没有联通,则输出 0。
    
    【思路】
    普通的并查集,每次还要记录下t[u],t[u]表示u号军工厂和它的父亲是什么时候连接上的。那么对于u和v,如果它们连通,那么就是u->lca(u,v)->v这条路径上t[u]的最大值。
    
    Sample Input
    5 9
    0 1 4
    1 2 5
    0 2 4
    0 3 4
    1 3 1
    0 7 0
    0 6 1
    0 1 6
    1 2 6
    Sample Output
    0
    3
    5
    
    
    
    
    
    合并两树根:取两根小值在左且为新根,合并新根右儿与另一树根至递归归并完,按深度换左右树,更新深度域
    删树根:先找根 读出 然后合并左右子树 
    
    

     

    展开全文
  • 启发式合并专题: LOJ#3052「十二省联考2019」春节十二响 贪心+启发式合并 bzoj3123 & 洛谷3302 [SDOI2013]森林 启发式合并+主席树+并查集
    展开全文
  • 启发式合并简介

    2018-09-12 21:37:00
    什么是启发式合并 启发式合并方法 复杂度分析 什么是启发式合并 启发式合并, 就是把n个大小为1的集合合并为一个大小为n的集合的一种方法. 其复杂度为\(O(n\log n)\) 这种方法被广泛应用在各种毒瘤数据结构...

    什么是启发式合并

    启发式合并, 就是把n个大小为1的集合合并为一个大小为n的集合的一种方法. 其复杂度为\(O(n\log n)\)

    这种方法被广泛应用在各种毒瘤数据结构(树套树)中.....

    当然, 集合合并操作的顺序是给定的(可以理解为强制在线)....(否则不就是\(O(n)\)了吗)...

    启发式合并方法

    启发式合并的算法很简单, 就是当要合并两个集合 \(s1, s2\)时, 将大小较小的合并至大小较大的

    //伪代码
    if(|s1| < |s2|) 
        for all x in s1: s2.insert(x);
        clear(s1);
    else 
        for all x in s2: s1.insert(x);
        clear(s2);

    复杂度分析

    为啥这个优化有这么好的效果呢?

    复杂度证明: 考虑贡献法.

    一个元素从一个集合被加入另一个集合时, 所在集合的规模至少扩大一倍. 如果没有分离操作且元素数目有限, 合并的次数是O(log n)的.

    因为有n个元素, 所以复杂度O(n log n)

    将其复杂度式写为 \(T(n) = \max_{k\in[1, n]}(T(k)+T(n-k)+\min(k, n-k)\ )\)

    通过以上证明, 所有类似这样的递归式, 其解都是 \(O(n\log n)\)

    转载于:https://www.cnblogs.com/Eroad/p/9637546.html

    展开全文
  • 树上启发式合并

    2020-07-12 10:47:07
    树上启发式合并 前言: 今天又遇到启发式合并了,还没有写出来,还是整理一下。 什么时候用启发式合并? 当需要统计并合并子树的信息,然而一次合并的复杂度为O(n)O(n)O(n),整体复杂度为O(n2)O(n^2)O(n2)时,使用...

    树上启发式合并

    前言: 今天又遇到启发式合并了,还没有写出来,还是整理一下。

    什么时候用启发式合并?

    当需要统计并合并子树的信息,然而一次合并的复杂度为 O ( n ) O(n) O(n),整体复杂度为 O ( n 2 ) O(n^2) O(n2)时,使用启发式合并可以将合并的复杂度降为 O ( n l o g n ) O(nlogn) O(nlogn)

    启发式合并的思想

    举一个例子,现在有一棵树,每个节点涂有一个颜色。需要统计每颗子树上哪种颜色最多。
    暴力合并:

    //实际上有更简洁的代码,这么写是为了和后面的启发式合并的代码做比较,有更直观的感受。
    nt n;//size of tree
    vector<int> tree[maxn];
    int color[maxn];//color on node
    int ans[maxn];// ans for each node
    int cnt[maxn];//used for cnt color on subtree
    int dfs(int rt, int fa, int *cnt)
    {
    	for(auto v : tree[rt])
    	{
    		if(v == fa)continue;
    		ans[v] = dfs(v, rt, cnt);
    		memset(cnt, 0, sizeof(cnt));
    	}
    	for(auto v : tree[rt])
    	{
    		if(v == fa)continue;
    		dfs(v, rt, cnt);
    	}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            
    	cnt[color[rt]]++;
    	int mx = -1, pos = 0;
    	for(int i = 1; i <= colorMax; ++i)
    		if(mx < cnt[i])mx = cnt[i], pos = i;
    	return pos;
    }
    

    上面的算法流程可以总结为:

    1. 统计子节点的信息并记录子节点答案
    2. 重新统计子节点的信息,合并在一块
    3. 加入父亲节点信息,计算答案

    每颗子树被统计至少一遍,复杂度 O ( n 2 ) O(n^2) O(n2)
    思考,可不可以在统计子节点信息,直接把子节点信息写入父亲节点相关数据结构,而不需要合并。
    答案是,只能选一个子节点在统计时直接写入父亲节点数据结构。如果选重儿子这么做,就是树上启发式合并。

    算法流程

    1. 统计轻儿子的信息并记录轻儿子的答案
    2. 统计重儿子的信息记录答案,同时保留重儿子的信息
    3. 将轻儿子的信息加入记录
    4. 加入父亲节点信息,计算答案。

    每个节点点被统计的次数为到根节点路径上轻链的数量 + 1,由于一条路径上轻链的个数不会超过 l o g n logn logn条,所以算法的复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

    大概代码:

    int n;//size of tree
    vector<int> tree[maxn];
    int color[maxn];//color on node
    int ans[maxn];// ans for each node
    int cnt[maxn];//used for cnt color on subtree
    int son[maxn];// heavy son
    
    int dfs(int rt, int fa, int *cnt)
    {
    	if(!son[rt])//a leaf
    	{
    		cnt[color[rt]]++;
    		return;
    	}
    	
    	//cal light son
    	for(auto v : tree[rt])
    	{
    		if(v == son[rt] || v == fa)continue;
    		ans[v] = dfs(v, rt, cnt);
    		memset(cnt, 0, sizeof(cnt));
    	}
    	//cal heavy son and remain the data
    	dfs(son[rt], rt, cnt);
    	//add light son data to get rt ans
    	for(auto v : tree[rt])
    		if(v == fa || v == son[rt])continue;
    		else dfs(v, rt, cnt);
    	cnt[color[rt]]++;
    	int mx = -1, pos = 0;
    	for(int i = 1; i <= colorMax; ++i)
    		if(mx < cnt[i])mx = cnt[i], pos = i;
    	return pos;
    }
    
    展开全文
  • 树上启发式合并算法概述及习题

    千次阅读 2019-10-28 08:50:42
    树上启发式合并概述 一、适用问题 树上启发式合并作为树上问题三剑客之一(点分治、长链剖分),以其优雅的暴力而闻名于江湖之中。 通常来说,如果一个问题可以被划分为一个个子树进行求解的问题,而且各个子儿子对...
  • 启发式合并入门

    2020-01-11 17:51:57
    所谓启发式合并,就是一种符合直觉的合并方法:将小的子树合并在大的子树上。 这些问题一般是相似的问题背景:都是树上的计数问题,都不能直接从上往下进行暴力,都需要从下往上计数时对子树信息进行运算从而得到...
  • 启发式合并 将小的集合一个个插入到大的集合。 每次新集合大小至少比小集合大一倍,因此每个元素最多合并\(\log n\)次,总复杂度为\(n\log n\) × 插入复杂度。 splay合并 将小的splay按中序遍历一个个插入到大的...
  • 树上启发式合并 cf600E

    2020-02-05 21:44:21
    树上启发式合并 这个是啥? 先说一下并查集的启发式合并: 并查集的启发式合并就是把集合小的并到集合大的上去。(按秩合并是把低的并到高的上面去) 于是树上的也差不多: 就这样一个优化的思路。把大的并到小的上去 ...
  • 树上启发式合并总结

    千次阅读 多人点赞 2018-11-30 14:09:45
    某一天发现一道树上启发式合并裸题,但我不会写…… 学习并刷了两天的题,是时候来写个总结了 正文 树上启发式合并(DSU on Tree),是一个在O(nlogn)O(nlogn)O(nlogn)时间内解决许多树上问题的有力算法。 但它的...
  • Hdu 6133 启发式合并

    2017-08-17 22:52:36
    第一次写启发式合并。。 大概就是大的子树只更新一次,把小的子树往大的里面抽插(233)。。 然后就可以了。。 唯一的问题是我代码能力十分捉急,写出了n个bug。。//启发式合并get //NJU很牛逼啊 //这个sumofsum...
  • 启发式合并】(dsu on tree)讲解+例题 超级好的讲解(来自cf) 1、启发式合并的作用: With dsu on tree we can answer queries of this type: How many vertices in the subtree of vertex v has some ...
  • 启发式合并的浅谈

    2020-07-25 19:00:55
    启发式合并的浅谈 0.定义 人凭借直觉和经验认为某种较优的策略对算法进行优化。 具体来说:将两个数据结构合并时,将较少的数据结构的元素一个个插入到较大的数据结构。 1.时间复杂度 每次合并复杂度最坏是:O(n)O...
  • BZOJ 2809(优先队列+启发式合并
  • 并查集的启发式合并

    2017-10-16 21:01:12
    在原来刚接触并查集的时候,感觉确实很方便,也是认为并查集就那么点东西,简单方便,但是后来无意间发现了一个并查集的启发式合并,可以对并查集进行优化,它优化的理论是用一个数组来记录每个节点的深度,每一次...
  • 启发式合并学习笔记

    2018-03-06 20:21:00
    树上启发式合并学习笔记 博客 https://www.cnblogs.com/zzqsblog/p/6146916.html http://codeforces.com/blog/entry/44351 题目 CF600E 题解 CF570D CF741D CF932F(斜率优化) TBD 转载于:...
  • Codeforces 600E Lomsat gelral (启发式合并)题目大意: 一棵树,每个点有一个颜色,每一次询问在u节点为根的子树中,颜色出现次数最多的那些颜色的和。 考虑启发式合并,每个节点开map,cnt[u][i]表示u节点为根...
  • dsu on tree(树上启发式合并)详解

    千次阅读 2019-11-08 10:08:35
    树上启发式合并详解。
  • 【算法】树上启发式合并算法

    千次阅读 2017-03-25 17:22:50
    树上启发式合并算法是启发式合并算法在树上的应用。下面我直接通过一个例子来讲解这个算法。  例:给定一棵有根树,树的结点编号为1~n,根结点为结点1。结点i有颜色col[i],其中1≤col[i]≤n。要求回答m个询问,每...
  • 启发式合并​ 有nn个集合,每次让你合并两个集合,或询问一个集合中是否存在某个元素。​ 我们可以用平衡树/set维护集合。​ 对于合并两个A,BA,B,如果|A|<|B||A|<|B|,那么我们就把AA中的每个元素暴力加到BB中,...
  • hiho 1561 观光旅行 [set启发式合并+想法]
  • 树上启发式合并入门

    2019-08-07 18:38:00
    树上启发式合并,即\(DSU\ on\ Tree\),是一个挺好用、挺实用的树上信息维护方法。 由于它比较简单,容易理解,因此这里也就简单记录一下吧。 前置知识:重儿子 什么是重儿子? 这应该是树链剖分中的一个概念吧。重...
  • 并查集 启发式合并 并查集,这是个比较简单的东西,用森林模拟集合,集合合并则是两颗树的合并,查找集合则是寻找某棵树的根节点 因为不可避免的会遇到各种合并操作,,所以可能导致某棵树的深度较大,,对应的则...
  • 本孱弱就献上一发线段树区间合并+启发式合并的垃圾解法。 首先,连续的碟子只用一次移动,体现在给出的数组( 碟子属于哪一个圆柱的编号)中为连续的元素相同: 比如: 1 2 3 3 2 4, 需要4次移动,第6个碟子不需要...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 20,491
精华内容 8,196
关键字:

启发式合并