Bzoj 2733: [HNOI2012]永无乡(线段树+启发式合并)

2023-12-25 15:58

本文主要是介绍Bzoj 2733: [HNOI2012]永无乡(线段树+启发式合并),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2733: [HNOI2012]永无乡
Time Limit: 10 Sec Memory Limit: 128 MB
Description
永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的。现在有两种操作:B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询问当前与岛 x连通的所有岛中第 k 重要的是哪座岛,即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪 座,请你输出那个岛的编号。
Input
输入文件第一行是用空格隔开的两个正整数 n 和 m,分别 表示岛的个数以及一开始存在的桥数。接下来的一行是用空格隔开的 n 个数,依次描述从岛 1 到岛 n 的重要度排名。随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi,表示一开始就存 在一座连接岛 ai 和岛 bi 的桥。后面剩下的部分描述操作,该部分的第一行是一个正整数 q, 表示一共有 q 个操作,接下来的 q 行依次描述每个操作,操作的格式如上所述,以大写字母 Q 或B 开始,后面跟两个不超过 n 的正整数,字母与数字以及两个数字之间用空格隔开。 对于 20%的数据 n≤1000,q≤1000
对于 100%的数据 n≤100000,m≤n,q≤300000
Output
对于每个 Q x k 操作都要依次输出一行,其中包含一个整数,表 示所询问岛屿的编号。如果该岛屿不存在,则输出-1。
Sample Input
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3
Sample Output
-1
2
5
1
2

/*
线段树+启发式合并.
对于每个叶节点建立一棵权值线段树.
然后发现对于每个联通块的值域是一样的.
然后就可以合并辣.
貌似这题还可以搞splay+启发合并
复杂度是O(nlogn2).
期望重构次数是nlogn次,每一次重构需要更新一条链,复杂度是logn的,
所以总复杂度是nlogn2的.
如果用平衡树的话也是nlogn2的.
某度贴吧中说用Finger Search可以降一个log.
但是好像没找到这方面的资料orz.
*/
#include<iostream>
#include<cstdio>
#define MAXN 100001
using namespace std;
int n,m,q,tot,root[MAXN],a[MAXN],father[MAXN],size[MAXN],s[MAXN];
struct data{int lc,rc,size;}tree[MAXN*20];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
int find(int x)
{return x!=father[x]?father[x]=find(father[x]):x;
}
void add(int &k,int l,int r,int x)
{if(!k) k=++tot;if(l==r){tree[k].size=1;return ;}int mid=(l+r)>>1;if(x<=mid) add(tree[k].lc,l,mid,x);else add(tree[k].rc,mid+1,r,x);tree[k].size=tree[tree[k].lc].size+tree[tree[k].rc].size;return ;
}
int query(int k,int l,int r,int x)
{if(l==r) return l;int mid=(l+r)>>1;if(tree[tree[k].lc].size>=x) return query(tree[k].lc,l,mid,x);else return query(tree[k].rc,mid+1,r,x-tree[tree[k].lc].size);
}
int slove(int x,int y)
{if(!x) return y;if(!y) return x;tree[x].lc=slove(tree[x].lc,tree[y].lc);tree[x].rc=slove(tree[x].rc,tree[y].rc);tree[x].size=tree[tree[x].lc].size+tree[tree[x].rc].size;return x;
}
int main()
{int x,y,k;char ch[3];n=read(),m=read();for(int i=1;i<=n;i++) a[i]=read(),father[i]=i,s[a[i]]=i;for(int i=1;i<=m;i++){x=read(),y=read();int l1=find(x),l2=find(y);father[l1]=l2;}for(int i=1;i<=n;i++){int l1=find(i);add(root[l1],1,n,a[i]);}q=read();while(q--){scanf("%s",ch);if(ch[0]=='Q'){x=read(),k=read();int l1=find(x);if(tree[root[l1]].size<k) printf("-1\n");else printf("%d\n",s[query(root[l1],1,n,k)]);}else{x=read(),y=read();int l1=find(x),l2=find(y);if(l1!=l2) {father[l2]=l1;root[l1]=slove(root[l1],root[l2]);}}}return 0;
}

这篇关于Bzoj 2733: [HNOI2012]永无乡(线段树+启发式合并)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/536072

相关文章

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col

Python视频剪辑合并操作的实现示例

《Python视频剪辑合并操作的实现示例》很多人在创作视频时都需要进行剪辑,本文主要介绍了Python视频剪辑合并操作的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录介绍安装FFmpegWindowsMACOS安装MoviePy剪切视频合并视频转换视频结论介绍

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在

在C#中合并和解析相对路径方式

《在C#中合并和解析相对路径方式》Path类提供了几个用于操作文件路径的静态方法,其中包括Combine方法和GetFullPath方法,Combine方法将两个路径合并在一起,但不会解析包含相对元素... 目录C#合并和解析相对路径System.IO.Path类幸运的是总结C#合并和解析相对路径对于 C

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que