最近在尝试参加一些算法比赛,遇到一个并查集的题目,虽然之前学过,但是没怎么刷题所以就忘了,
于是花时间开始复习,遇到一些问题记录下来
并查集(待补)
倒序操作
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
分析
- 对于操作2,需要找到最大的\(y\),那么其他的比\(y\)小的数都为\(y\)
- 对于操作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\)。
分析
- 需要统计树的权值和,因此考虑使用并查集
- 每个节点带有编号,因此考虑带权并查集(其实就是新开一个数组存储权值和)
- 对于并查集来说,删除操作很麻烦,但是连接操作很方便 —— 把一个节点作为另一个节点的父节点,因此考虑倒序操作
- 根据题意,最后的结果应该是一个一个单独的树,各个操作对应的操作应该是:
- 连接插入的第\(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