首页 > 其他分享 >并查集(草稿)

并查集(草稿)

时间:2022-11-23 10:59:44浏览次数:45  
标签:opt 草稿 val int 查集 leq 权值 op

最近在尝试参加一些算法比赛,遇到一个并查集的题目,虽然之前学过,但是没怎么刷题所以就忘了,
于是花时间开始复习,遇到一些问题记录下来

并查集(待补)

倒序操作

452. 序列操作

题目链接

http://oj.daimayuan.top/problem/452

题目描述

给定一个长度为 \(n\) 的序列 \(a_1,a_2,\dots ,a_n\)。

你需要进行两种操作:

1、\(1\) \(x\) \(y\)——将第 \(x\) 个数变为 \(y\);

2、\(2\) \(y\)——将所有小于 \(y\) 的数修改为 \(y\);

共执行 \(q\) 次操作,输出执行完所有操作后的序列。

输入格式

第一行两个数字 \(n\) , \(q\) \((1 \leq n,q \leq 10^6)\)。
接下来一行 \(n\) 个整数 \(a_1, a_2, \dots, a_n\) \((0 \leq a \leq 10^9)\)。
接下来 \(q\) 行,每行表示一个操作: \(1\) \(x\) \(y\) 或 \(2\) \(y\) \((1 \leq x \leq n, 0 \leq y \leq 10^9)\)。

输出格式

一行整数,表示操作完后的序列,用空格分隔。

样例输入

3 6 14 16 12
2 13
2 16
1 1 1
1 2 14
2 11

样例输出

11 14 16 16 16

分析

  1. 对于操作2,需要找到最大的\(y\),那么其他的比\(y\)小的数都为\(y\)
  2. 对于操作1,只考虑最后一次改变\(x\)位置的操作,与最大的\(y\)的最大值

代码

#include<iostream>
#include<algorithm>
using namespace std;
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N=1000010;
int a[N];
int n,q;
int opt[N],x[N],y[N],v[N];
int main(){
	io;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int i=1;
    for(int i=1;i<=q;i++){
		cin>>opt[i]>>x[i];
		if(opt[i]==1) cin>>y[i];
	}
	int maxn=0;
	for(int j=q;j>=1;j--){
		if(opt[j]==1&&v[x[j]]==0){
			v[x[j]]=1;
			a[x[j]]=max(maxn,y[j]);
		}else if(opt[j]==2){
			maxn=max(maxn,x[j]);
		}
	}
	for(int j=1;j<=n;j++){
		if(v[j]==0){
			a[j]=max(maxn,a[j]);
		}
		cout<<a[j]<<' ';
	}
	cout << endl;
	
}

并查集+倒序

[传智杯 #5 练习赛] 树的变迁

题目链接

https://www.luogu.com.cn/problem/T292115?contestId=91314

题目描述

给定一棵具有 \(n\) 个节点的树,每个节点有一个初始权值 \(a_i\)。

一共需要进行 \(m\) 次操作,每次操作包括:

  • 1 e 编号为 \(e\) 的边突然消失,使得它所在的那棵树变成了两棵树。

  • 2 u val 编号为 \(u\) 的节点的权值变成了 \(val\)。

  • 3 u 进行了一次查询,查询 \(u\) 所在的那棵树的权值之和。

现在你需要来模拟上述事件,以了解树的变迁。

输入格式

第一行为 \(n, m\),如上所述。

第二行有 \(n\) 个数,为 \(n\) 个结点的初始权值,在 \(10^3\) 以内。

下面 \(n-1\) 行,每行一组 \(u, v\),表示一条边。(保证初始为一棵树)

下面 \(m\) 行有 \(m\) 个操作:

先读入一个 \(\text{opt}\),表示操作类型。

  • \(\text{opt}=1\) 时,读入 \(e\),表示删掉读入的第 \(e\) 条边。(保证第 \(e\) 条边存在)

  • \(\text{opt}=2\) 时,读入 \(u,val\),表示把结点 \(u\) 的权值改成 \(val\)(\(val \le 1000\))。

  • \(\text{opt}=3\) 时,读入 \(u\),表示查询 \(u\) 所在的那棵树的结点权值和。

输出格式

对于每个查询操作,输出一行一个数表示答案。

样例 #1

样例输入 #1

2 3
1 1
1 2
2 2 4
1 1
3 2

样例输出 #1

4

提示

所有测试数据数据满足 \(1 \leq n,m \leq {10}^5\),\(1 \leq a_i,val \leq 1000\)。

分析

  1. 需要统计树的权值和,因此考虑使用并查集
  2. 每个节点带有编号,因此考虑带权并查集(其实就是新开一个数组存储权值和)
  3. 对于并查集来说,删除操作很麻烦,但是连接操作很方便 —— 把一个节点作为另一个节点的父节点,因此考虑倒序操作
  4. 根据题意,最后的结果应该是一个一个单独的树,各个操作对应的操作应该是:
    • 连接插入的第\(e\)条边
    • 把节点\(u\)的权值改为\(val\)
    • 查询\(u\)所在的树的权值之和

代码

#include<iostream>
#include<algorithm>
#define os ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=100010;
//记录操作
struct{
    int op,u,val,e,pre_val;
}opt[N];
//记录插入的边
struct{
    int u,v;
}Edge[N];
//记录祖宗节点、原始权重、不能连接的边的下标、最终权值、答案
int p[N],weight[N],v[N],val[N],ans[N];
int n,m;
//查找祖宗节点
int find(int x){
    if(p[x]!=x){
        int root=find(p[x]);
        p[x]=root;
    } 
    return p[x];
}
//连接两个节点
void merge(int u,int v){
    int x=find(u),y=find(v);
    p[y]=x;
    val[x]+=val[y];
    // p[x]=y;
    // val[y]+=val[x];
}
int main(){
    os;
    cin>>n>>m;
    for (int i = 1; i <= n; i++)
    {
        cin>>weight[i];
    }
    for (int i = 1; i < n; i++)
    {
        cin>>Edge[i].u>>Edge[i].v;
    }
    for (int i = 1; i <= m; i++)
    {
        int op;
        cin>>op;
        opt[i].op=op;
        if(op==1){
            cin>>op;
            v[op]=1;
            opt[i].e=op;
        }else if(op==2){
            int u,val;
            cin>>u>>val;
            opt[i].u=u;
            opt[i].val=val;
            opt[i].pre_val=weight[u];
            weight[u]=val;
        }else{
            cin>>op;
            opt[i].u=op;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        p[i]=i;
        val[i]=weight[i];
    }
    //形成最终的树
    for(int i=1;i<n;i++){
        if(!v[i]){
            merge(Edge[i].u,Edge[i].v);
        }
    }
    int j=0;
    for(int i=m;i>=1;i--){
        int op=opt[i].op;
        if(op==1){
            int u=opt[i].e;
            merge(Edge[u].u,Edge[u].v);
        }else if(op==2){
            int u=opt[i].u;
            int val1=opt[i].val;
            int pre_val=opt[i].pre_val;
            int root=find(u);
            val[root]-=val1;
            val[root]+=pre_val;
        }else{
            int u=opt[i].u;
            ans[j++]=val[find(u)];
        }
    }
    for(int k=j-1;k>=0;k--){
        cout<<ans[k]<<endl;
    }
    return 0;
}

标签:opt,草稿,val,int,查集,leq,权值,op
From: https://www.cnblogs.com/karson3/p/16916402.html

相关文章

  • ABC 214D Sum of Maximum Weights(并查集模拟删边)
    ABC214DSumofMaximumWeights(并查集模拟删边)SumofMaximumWeights​ 给出有\(n\;(2\len\le1e5)\)个点的一棵树,定义\(f(x,y)\)表示从节点x到节点y的最短......
  • 可撤销并查集学习笔记
    前言与可持久化并查集一起食用,效果更佳。前置知识:并查集以及并查集的按秩合并优化。例题引入你需要维护一棵\(n\)个点的动态森林,初始时是\(n\)个散点,有\(q\)个......
  • T292115 [传智杯 #5 练习赛] 树的变迁(并查集+倒序操作处理树分裂)
    T292115[传智杯#5练习赛]树的变迁题目大意:给定一棵具有\(n\)个节点的树,每个节点有一个初始权值\(a_i\)。一共需要进行\(m\)次操作,每次操作包括:1.1e编号......
  • 并查集
    title:并查集date:2022-11-1511:49:57tags:算法本文章遵守知识共享协议CC-BY-NC-SA,转载时需要署名,推荐在我的个人博客阅读。并查集是一种数据结构,用于合并两个......
  • 并查集教学
    并查集简介并查集是一个树形的数据结构,能够实现以下功能:将两个节点所属的两个集合合并查询两个节点是否在一个集合里并查集教学我们以洛谷的并查集板题为例P3367......
  • 草稿纸
    \[\begin{align*}&\sum_{i=1}^ni(n-i)\dbinomni\\=&n\sum_{i=1}^ni\dbinomni-\sum_{i=1}^ni^2\dbinomni\\=&n^2\sum_{i=1}^n\dbinom{n-1}{i-1}-n\sum_{i=1}^n......
  • 软考架构-论文练手草稿(面向服务-正文)
    本文结合笔者的实际工作经验,主要论述面向服务的架构在该项目中的具体应用。provider服务提供者主要完成服务的设计、描述、定义和发布等相关工作;registry服务注册中心保证该......
  • 排序 草稿
    //这里将map.entrySet()转换成list,再用collections工具类中的sort()方法完成排序操作List<Map.Entry<String,Long>>list=newArrayList<>(collect.entrySet())......
  • 落谷 R94681591 -- 并查集+离线算法+倒序处理
    题目描述树的变迁思路因为更改点的权值不会改变树的结构,但是删去一条边会改变树的结构,不同与增加一条边,删除一条边的处理是很麻烦(没实现过!!!)既然我们无法删除一条边,那么......
  • D. Mahmoud and a Dictionary(种类并查集)
    D.MahmoudandaDictionarytimelimitpertest4secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputMahmoudwantstowriteanewdi......