BZOJ2733: [HNOI2012]永无乡(线段树合并)_weixin_30823001的博客-程序员秘密

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

解题思路:

权值线段树合并,将并查集连接时将线段树合并,最后查询根节点的值就好了

代码:

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 struct trnt{
  5     int ls;
  6     int rs;
  7     int wgt;
  8 }tr[8000000],str;
  9 int fa[500000];
 10 int imp[500000];
 11 int root[500000];
 12 int island[500000];
 13 int siz;
 14 int n,m;
 15 int bin[6000000];
 16 int top;
 17 char cmd[100];
 18 void pushup(int spc)
 19 {
 20     if(!spc)    
 21         return ;
 22     tr[spc].wgt=tr[tr[spc].ls].wgt+tr[tr[spc].rs].wgt;
 23     return ;
 24 }
 25 int finf(int x)
 26 {
 27     return x==fa[x]?x:fa[x]=finf(fa[x]);
 28 }
 29 int new_p(void)
 30 {
 31     int ans;
 32     if(top)
 33         ans=bin[top--];
 34     ans=++siz;
 35     tr[ans]=str;
 36     return ans;
 37 }
 38 void del(int &spc)
 39 {
 40     bin[++top]=spc;
 41     spc=0;
 42     return ;
 43 }
 44 void build(int &spc,int l,int r,int pos)
 45 {
 46     if(!spc)
 47         spc=new_p();
 48     tr[spc].wgt++;
 49     if(l==r)
 50         return ;
 51     int mid=(l+r)>>1;
 52     if(pos<=mid)
 53         build(tr[spc].ls,l,mid,pos);
 54     else
 55         build(tr[spc].rs,mid+1,r,pos);
 56     return ;
 57 }
 58 int merge(int spc1,int spc2,int l,int r)
 59 {
 60     if(!spc1||!spc2)
 61         return spc1+spc2;
 62     int spc=new_p();
 63     if(l==r)
 64     {
 65         tr[spc].wgt=tr[spc1].wgt+tr[spc2].wgt;
 66         return spc;
 67     }
 68     int mid=(l+r)>>1;
 69     tr[spc].ls=merge(tr[spc1].ls,tr[spc2].ls,l,mid);
 70     tr[spc].rs=merge(tr[spc1].rs,tr[spc2].rs,mid+1,r);
 71     pushup(spc);
 72     del(spc1);
 73     del(spc2);
 74     return spc;
 75 }
 76 int kth(int l,int r,int k,int spc)
 77 {
 78     if(l==r)
 79         return l;
 80     int mid=(l+r)>>1;
 81     if(tr[spc].wgt<k)
 82         return -1;
 83     if(tr[tr[spc].ls].wgt>=k)
 84         return kth(l,mid,k,tr[spc].ls);
 85     else
 86         return kth(mid+1,r,k-tr[tr[spc].ls].wgt,tr[spc].rs);
 87 }
 88 int main()
 89 {
 90     scanf("%d%d",&n,&m);
 91     for(int i=1;i<=n;i++)
 92     {
 93         scanf("%d",&imp[i]);
 94         fa[i]=i;
 95         build(root[i],1,n,imp[i]);
 96         island[imp[i]]=i;
 97     }
 98     for(int i=1;i<=m;i++)
 99     {
100         int a,b;
101         scanf("%d%d",&a,&b);
102         int fx=finf(a);
103         int fy=finf(b);
104         if(a!=b)
105         {
106             fa[fx]=fy;
107             root[fy]=merge(root[fx],root[fy],1,n);
108         }
109     }
110     int q;
111     scanf("%d",&q);
112     while(q--)
113     {
114         scanf("%s",cmd+1);
115         int x,y;
116         scanf("%d%d",&x,&y);
117         if(cmd[1]=='B')
118         {
119             int fx=finf(x);
120             int fy=finf(y);
121             if(fy!=fx)
122             {
123                 fa[fx]=fy;
124                 root[fy]=merge(root[fx],root[fy],1,n);
125             }
126         }else{
127             int f=finf(x);
128             int no=kth(1,n,y,root[f]);
129             if(no==-1)
130                 printf("%d\n",-1);
131             else
132                 printf("%d\n",island[no]);
133         }
134     }
135     return 0;
136 }

 

转载于:https://www.cnblogs.com/blog-Dr-J/p/9726340.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30823001/article/details/98760583

智能推荐

阿翔编程学-工作流_java_xiang的博客-程序员秘密

 工作流工作流历史 工作流技术发端于 1970 年代中期办公自动化领域的研究工作,但工作流思想的出现还应该更早, 1968 年 Fritz Nordsieck 就已经清楚地表达了利用信息技术实现工作流程自动化的想法。 1970 年代与工作流有关的研究工作包括:宾夕法尼亚大学沃顿学院的 Michael D. Zisman 开发的原型系统 SCOOP ,施乐帕洛阿尔托研究中心的 Clarenc

2017美国数学建模ICM E题(环境) 翻译 需要可持续城市!(Sustainable Cities Needed!)_JIAN_BOY_RISE的博客-程序员秘密

问题E:需要可持续城市!((Sustainable Cities Needed!))背景:许多社区正在实施智能增长计划,以考虑长期,可持续的规划目标。 “聪明的成长是关于帮助每个城镇和城市变得更加经济繁荣,社会公平和环境可持续的生活地方。”[2]智能增长的重点是建设拥抱可持续发展的城市 - 经济繁荣,社会公平,环境可持续。这个任务比以往任何时候都重要,因为世界正在迅速城市化。预计到2050

html+css实现多种动态相册_html导入照片合集_皇家小骑士的博客-程序员秘密

电子相册全屏背景切换照片墙百叶窗3d照片墙立方体相册代码

java properties报错_javaProperties配置文件读取_britviola的博客-程序员秘密

在java中,可读取的配置文件一般包含xml和Properties,现在单讲Properties。Properties配置文件的格式:key1= valueskey2= values2。。。。。。注意:values不需要添加引号,直接键入值,等号左右可添加空格对齐,在其他行,可用#注释。如:#姓名:username= root#密码:password= 123456#其他:ip= localhos...

登录linux图形界面authentication failed提示解决_pscjinn的博客-程序员秘密

用一般用户登录linux图形界面,其实登录命令行界面也会提示,这是因为用户修改了linux用户验证机制导致的。切换root用户运行system-config-authentication 验证设置为下图即可:

随便推点

让C++控制台程序停下来,实现暂停功能_c++面板停流_普通网友的博客-程序员秘密

让C++控制台程序停下来,实现暂停功能 一、针对Microsoft #include &amp;lt;stdlib.h&amp;gt; (1)第一种方式 system(

python抓取彩票数据_用 Python 抓取分析十年彩票中奖结果_我不取名的博客-程序员秘密

用 Python 抓取分析十年彩票中奖结果在爬取一些简单的 (没有反爬机制的) 静态网页时, 一般采取的策略是: 选中目标(所谓的 url 链接), 观察结构(链接结构, 网页结构), 构思动手(选用什么 html 下载器, 解析器等).前两天, 在网上看到一个有意思的问题: 彩票预测靠谱么? 为什么还有那么多的人相信彩票预测?暂且不说, 彩票预测是否靠谱? 彩票预测也分人而异, 江湖上骗术很多,...

JumpServer堡垒机登入服务器下载文件提示无效的服务器端响应. 服务端发生错误. HTTP error 504_jumpserver一直下不了_玩电脑的辣条哥的博客-程序员秘密

环景:Ubuntu16.04本地华为桌面云服务器环境问题描述:JumpServer堡垒机登入服务器下载文件提示无效的服务器端响应. 服务端发生错误. HTTP error 504解决方案:1.先查询要下载文件夹大小及个数里面文件个数太多导致失败2.压缩相应文件夹.zip文件命令 unzip -O cp936 filename.zip # 解压(不乱码) zip filename.zip dirname #

docx4j -- 使用Java处理word2007(.docx)文档_docx4j 使用_ 玄月初心的博客-程序员秘密

前面的话最近的项目中很多地方需要处理Microsoft的word2007文档(即.docx文档),本来打算用Apache的POI项目,但经过试用发现其对word2007的支持并不好(其实可以说很差),网络上大家也都在讨论这个问题,说POI其实只是个半成品(仅仅是针对office2007这一块来说),并不推荐使用。所以我又多方查找解决方案,最终找到了docx4j项目,docx4j主要用于

kubernetes--k8s--web管理界面使用--dashboardv1.8.3版本安装详细步骤_张小凡vip的博客-程序员秘密

安装dashboard监控界面 (仅主节点运行)dashboard官网参考使用命令kubectl create -f https://raw.githubusercontent.com/kubernetes/dashboard/master/src/deploy/recommended/kubernetes-dashboard.yaml输出如下:[[email protected] kubernetes...

辛星Java动态规划教程第三篇:最长公共子串(LCS)_辛星的博客-程序员秘密

上一篇介绍到最长公共子序列,这一篇就来介绍下最长公共子串,即最长公共子字符串。也就是Longest Common Substring,通常也被简称为LCS,比较尴尬的是和上一篇的简称是重名的。要求最长公共子串,思路有很多,这里介绍两种,但是实现上是相同的,只是初始思路不同:第一种,比较常规且自然的思路就是对于字符串a和b,构造一个二维数组arr,其中arr[i][j]表示第a[i]和b[j]是...

推荐文章

热门文章

相关标签