POJ – 2492 – A Bug’s Life (种类并查集)

题目链接:POJ - 2492 题目大意: 一种动物有两种性别,假设不同性别才能进行配对, 给出配对情况,问是否存在同性配对的情况。 题目分析: 种类并查集。 用a和a+n代表两种性别。 如果a和b在一个并查集内,则同性。 给出代码: #include <cstring> #i…

POJ – 3321 – Apple Tree (树状数组,DFS序,模板)

题目链接:POJ - 3321 题目大意: 有一颗树,根永远为1. 初始状态每个节点上的值都为1 有两种操作: 查询某一节点子树上所有节点和的值 将某一节点值取非 题目分析: 利用DFS序将树转变成线性区间结构,然后利用树状数组即可。 注意:莫名奇妙的卡vector,要用 vector<vec…

POJ – 3368 – Frequent values (RMQ查询,模板)

题目链接:POJ - 3368  题目大意: 给一段非降序数列,查询在区间[X,Y]之间出现次数最多的数字。 题目分析: 先将所有数进行游程编码。 num[p],left[p],right[p]分别表示位置p所在段的编号和左右端点位置。 这样查询时,就只需要单独计算左端点段的部分次数,右端…

HDU – 3887 – Counting Offspring(DFS序+线段树)

题目链接:HDU - 3887 题目大意:问你对于每个节点,它的子树上标号比它小的点有多少个  题目分析: 利用DFS序建立一个初始节点值都为0的线段树。 每次先查询值,然后讲该点加入到线段树里面去。 给出代码: #include <iostream> #includ…