【BZOJ 2733】 [HNOI2012]永无乡|Splay启发式合并

2024-03-02 21:48

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

代码能力太弱

#include <cstdio>
#include <iostream>
#include <algorithm> 
using namespace std;
#define MAXN 100010
int father[MAXN],root[MAXN];
int fa[MAXN],to[MAXN][2],size[MAXN],num[MAXN],id[MAXN];
int n,m;
int laji[MAXN],top;
void Up(int x){ size[x]=size[to[x][0]]+size[to[x][1]]+1; }
void Rotate(int &rt,int x)
{int y=fa[x],z=fa[y];if(y==rt) rt=x;else to[z][to[z][1]==y]=x;int c=to[y][1]==x;fa[x]=z;fa[y]=x;fa[to[x][c^1]]=y;to[y][c]=to[x][c^1];to[x][c^1]=y;Up(y);Up(x); 
}
void Splay(int &rt,int x)
{while(rt!=x){if(fa[x]!=rt) Rotate(rt,fa[x]);Rotate(rt,x);}
}
void Ins(int &now,int &rt,int ID,int NUM,int last)
{if(now==0){now=laji[top--];num[now]=NUM;id[now]=ID;fa[now]=last;size[now]=1;Splay(rt,now);return ;}if(NUM<=num[now]) Ins(to[now][0],rt,ID,NUM,now);else Ins(to[now][1],rt,ID,NUM,now);
}
void Dfs(int &rt,int now)
{if(now==0) return ;Dfs(rt,to[now][0]);Dfs(rt,to[now][1]);Ins(rt,rt,id[now],num[now],0);fa[now]=to[now][0]=to[now][1]=size[now]=id[now]=num[now]=0;laji[++top]=now;
}
int F(int x)
{if(father[x]!=x) father[x]=F(father[x]);return father[x];
}
void Link(int x,int y)
{x=F(x);y=F(y);if(x==y) return ;int sx=size[root[x]];int sy=size[root[y]];if(sx<sy) swap(x,y);Dfs(root[x],root[y]);father[y]=x;
}
int Q(int now,int k)
{if(now==0) return -1;int tmp=size[now]-size[to[now][1]];if(tmp==k) return id[now];else if(tmp<k) return Q(to[now][1],k-tmp);else return Q(to[now][0],k);
}
int main()
{cin >>n >>m;int x,y,q;char s[20];for(int i=1;i<MAXN;i++) laji[++top]=i;for(int i=1;i<MAXN;i++) father[i]=i; for(int i=1;i<=n;i++) scanf("%d",&x),Ins(root[i],root[i],i,x,0);for(int i=1;i<=m;i++) scanf("%d %d",&x,&y),Link(x,y);cin >>q;while(q--){scanf("%s %d %d",s+1,&x,&y);	if(s[1]=='Q') printf("%d\n",Q(root[F(x)],y));else Link(x,y);}return 0;
}


这篇关于【BZOJ 2733】 [HNOI2012]永无乡|Splay启发式合并的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

【Python从入门到进阶】64、Pandas如何实现数据的Concat合并

接上篇《63.Pandas如何实现数据的Merge》 上一篇我们学习了Pandas如何实现数据的Merge,本篇我们来继续学习Pandas如何实现数据的Concat合并。 一、引言 在数据处理过程中,经常需要将多个数据集合并为一个统一的数据集,以便进行进一步的分析或建模。这种需求在多种场景下都非常常见,比如合并不同来源的数据集以获取更全面的信息、将时间序列数据按时间顺序拼接起来以观察长期趋势等

线性表中顺序表的合并

对两个顺序表进行合并,算法的复杂度为O(La.size+Lb.size)。 已知: 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc,Lc的元素也按值非递减排列。 代码定义: void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b

为libpng不同架构创建构建目录、编译、安装以及合并库文件的所有步骤。

好的。既然你已经有了 libpng 的源代码,并且当前处在它的目录下,我们可以简化脚本,不再需要下载和解压源代码这一步。以下是修改后的脚本:```sh#!/bin/bash# 当前目录即 libpng 源代码目录LIBPNG_SRC_DIR=$(pwd)# 设置工作目录WORK_DIR=$(pwd)/libpng_buildBUILD_DIR_X86_64="$WORK_DIR/build

listview与复选框的合并使用

在使用listview的过程中,我们常常需要使用复选框,实现一些批处理功能。这时候我们需使用自定义的adapter,实现相关复选框的事件响应。      首先在adapter定义一个哈希表,用于存放复选框的选中情况:      如private static HashMap<String,Boolean> isSelected,private static HashMap<Inter

ZOJ 3324 Machine(线段树区间合并)

这道题网上很多代码是错误的,由于后台数据水,他们可以AC。 比如这组数据 10 3 p 0 9 r 0 5 r 6 9 输出应该是 0 1 1 所以有的人直接记录该区间是否被覆盖过的方法是错误的 正确方法应该是记录这段区间的最小高度(就是最接近初始位置的高度),和最小高度对应的最长左区间和右区间 开一个sum记录这段区间最小高度的块数,min_v 记录该区间最小高度 cover

【Markdown】如何在Markdown中合并单元格

Markdown语法本身不包含复杂表格的插入,但是可以使用html语法来实现。 水平单元格的合并:基于colspan属性,即使一个单元格占多列的空间纵向单元格的合并:基于rowspan属性,即使一个单元格占多行的空间 要想MarkDown中插入复杂表格时,可以先在word或excel中把表格写好,然后在如下网站进行转化为标记对形式: http://pressbin.com/tools/exc

【Leetcode56】合并区间(数组 | 排序)

文章目录 一、题目二、思路三、代码 一、题目 二、思路 先将所有子列表按照start_pos进行排序,有利于保持顺序性,每次处理新子列表时,只用和结果列表ans_lst的最后一个子列表对比,如果有重合则合并,然后将合并的新子列表插入结果列表排序可以使用lambda函数,intervals.sort(key=lambda x: x[0])因为使用了sort,所以时间复杂度O(