数据结构
单链表
本部分用数组模拟
单链表几个常用的操作，初始化，删除下标为k-1的元素，在头结点插入元素，在下标为k-1的元素后面插入一个元素 。
模板：
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点 int head, e[N], ne[N], idx; // 初始化 void init() { head = -1; idx = 0; } // 在链表头插入一个数a void add_head(int a) { e[idx] = a, ne[idx] = head, head = idx ++ ; } //在下标为k-1的元素后插入一个元素 void insert(int k,int x) { e[idx]=x; ne[idx]=ne[k]; ne[k]=idx; idx++; } // 将头结点删除，需要保证头结点存在 void remove() { head = ne[head]; } //如果删除头结点，即：k为0时，直接head=ne[head]即可，需要特判
题目链接[单链表](826. 单链表 - AcWing题库)
代码如下：
//数组模拟单链表 常用于：邻接表存储图和树
#include<bits/stdc++.h>
using namespace std;
const int N =100010;
//head表示头指针，e存元素值，ne存next指针，idx指向当前操作的结点
int e[N],ne[N],idx,head;
//初始化
void init() {
head=-1; //头指针指向空
idx=0; 表示从第一个结点开始使用
}
//插入到头结点位置
void add_head(int x) {
e[idx]=x; 待插入结点的准备
ne[idx]=head;
head=idx; 头指针重新指向头结点
idx++; 开始处理下一个位置
}
//将元素插入到下标为k的后面 即：在idx下标为k-1的点的后面加一个元素
void add(int k,int x) {
e[idx]=x; idx在每次插入后都会后移到最后一个元素的下一个位置，所以不用担心会误修改
ne[idx]=ne[k]; 先指向k的下一个结点，前面再接上k
ne[k]=idx;
idx++;
}
//删除下标为k的点的后一个点 即：删除idx下标为k-1的点
void del(int k) {
ne[k]=ne[ne[k]];
}
注意idx就算插入元素后再删除该元素，idx也不会回溯，而是一直往后，这样就完成了题目要求的第k个数（第k个插入的数）
int main() {
int m;
cin>>m;
init(); //初始化
while(m--) {
int k,x;
char c;
cin>>c;
if(c=='H') {
cin>>x;
add_head(x);
} else if(c=='D') {
cin>>k;
if(!k) head=ne[head]; 特判，当删除头结点时，head指针直接指向头结点的下一个指针即可
del(k-1);
} else if(c=='I') {
cin>>k>>x;
add(k-1,x);
}
}
//遍历，从头结点开始走
for(int i=head; i!=-1; i=ne[i]) {
cout<<e[i]<<" ";
}
cout<<endl;
return 0;
}双链表
为省事，将存放元素的数组e的0和1下标对应位置分别存放头和尾指针，这样的话idx就从2开始存元素，因此第k个插入的元素下标对应k+1 .这点要谨记。
模板：
//e存元素value，l存左指针，r存右指针,idx指向当前操作结点 int e[N],l[N],r[N],idx; //初始化 void init(){ //为省事，0表示左端点head，1表示右端点tail r[0]=1; l[1]=0; 两端点head和tail分别为对方的左右指针,形成初始闭环 idx=2; 0和1已经用于头尾指针了，从2开始存元素 } //在下标为k的点的右边插入一个数x void add(int k,int x){ e[idx]=x; //改四条指针的指向 l[idx]=k; 将新结点的左指针指向k r[idx]=r[k]; 将当前元素的右指针指向k的下一个元素 l[r[k]]=idx; 将原本k右边的数的左指针指向新插入的结点 r[k]=idx; idx++; } //如果在k的左边插入一个点，可以直接调用add([l[k]]) ; 即：在k的前一个元素的右边插入一个元素 //删除第k个元素 void remove(int k){ //令其左边的元素的右指针指向其右边的元素，将右边的元素的左指针指向其左边的元素 r[l[k]]=r[k]; l[r[k]]=l[k]; }
其中需要注意的是：
1.插入操作函数，默认为在下标为k+1的元素的右边插入一个元素，如果需要在其左侧插入一个元素，使用<add(l[k+1]);>即在其左边的数的右边插入该数。
2.元素从2开始存，所以第k个插入的数的下标对应k+1，如果将尾指针放在数组尾部，其实可以实现k下标对应k，但是废空间，可以视情况而定（待元素个数很多时，将尾指针定义到尾部）
3.插入元素到左右端，也是可以根据关系在0的右边和1的左边插入元素
对应<**add(0,x); add(l[1],x**);>
题目链接[双链表](827. 双链表 - AcWing题库)
完整代码如下：
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
const int N =100010;
//e存元素value，l存左指针，r存右指针,idx指向当前操作结点
int e[N],l[N],r[N],idx;
//初始化
void init(){
//为省事，0表示左端点head，1表示右端点tail
r[0]=1; l[1]=0; //两端点head和tail分别为对方的左右指针,形成初始闭环
idx=2; //0和1已经用于头尾指针了，从2开始存元素
}
//在下标为k的点的右边插入一个数x
void add(int k,int x){
e[idx]=x;
//改四条指针的指向
l[idx]=k; //将新结点的左指针指向k
r[idx]=r[k]; //将当前元素的右指针指向k的下一个元素
l[r[k]]=idx; //将原本k右边的数的左指针指向新插入的结点
r[k]=idx;
idx++;
}
//如果在k的左边插入一个点，可以直接调用add([l[k]]) ; 即：在k的前一个元素的右边插入一个元素
//删除第k个元素
void remove(int k){
//令其左边的元素的右指针指向其右边的元素，将右边的元素的左指针指向其左边的元素
r[l[k]]=r[k];
l[r[k]]=l[k];
}
//在最左端插入一个数 发现就是在0的右边插入一个数 ,在最右侧插入同理在1的左边插入
// void add_l(int x){
// e[idx]=x;
// r[idx]=r[0];
// l[idx]=0;
// l[r[0]]=idx;
// r[0]=idx++;
// }
int main(){
init();
int m;
cin>>m;
while(m--){
string c;
int k,x;
cin>>c;
if(c=="L"){
cin>>x;
add(0,x);
}else if(c=="R"){
cin>>x;
add(l[1],x); //在最右端插入一个元素相当于在1的左边元素的右边插入一个元素
}else if(c=="D"){
cin>>k;
remove(k+1); //这里注意第k个插入的点的下标应该是k+1，因为第一个插入的点在下标为2的位置
}else if(c=="IL"){
cin>>k>>x;
// cout<<l[k+1]<<"---------"<<endl;
add(l[k+1],x); //k+1同理对应第k个数
}else if(c=="IR"){
cin>>k>>x;
add(k+1,x);
}
}
//遍历双链表 从0头结点的下一个结点开始出发，直到遇到右尾结点1
for(int i=r[0];i!=1;i=r[i]){
cout<<e[i]<<" ";
}
cout<<endl;
return 0;
}栈和队列
看模板吧
哈希表
开放寻址法（最常用）
定义一个一维数组,大小一般开题目要求的2–3倍（2e5,3e5—）；
1.插入：利用哈希函数得到映射后的k，在数组的对应k位置插入该元素，如果位置已经存在一个元素了，就依次找空的位置插入。
2.查找：看第映射后的第k个位置，是不是有元素
（1）有元素，并且等于x （找到）
（2）有元素，但是不等于x ，则继续往后找 （如果不为空但是不等于x，可能是被占位了，x则被存在后面的位置或者不存在）
（3）无元素，则不存在x （因为如果当前为空，说明没有数映射到这个位置）
3.删除：并不是实际删除，而是用一个标记.(0x3f3f3f3f)(大于1e9的数，不在范围内)
主要部分find
当前位置不等于空位置时，并且不等于该元素时，找下一个可以插入的位置k++（注意k的最大取值，需要判断是否超过数组最大范围）
如果该位置为空，则返回可以插入的位置，即当前位置
代码如下：
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N =200003,null=0x3f3f3f3f;
int h[N];
int find(int x){
int k=(x%N+N)%N;
while(h[k]!=null && h[k]!=x){ //如果该位置不是空的并且不是x，则往后找
k++;
if(k==N) k=0;
}
return k;
}
int main(){
int n;
cin>>n;
//数组该位置为0x3f时 就认为空，因为不在数据范围内
memset(h,0x3f,sizeof h);
memset 以字节set，并且int类型，则4*0x3f 足以超过1e9
while(n--){
char c;int x;
cin>>c;
if(c=='I'){
cin>>x;
int k=find(x);
h[k]=x;
}else {
cin>>x;
int k=find(x);
if(h[k]!=null) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}拉链法（类似邻接表）
以数组h的每个元素为每个链表的头指针，如果某些数的k值相同，则插入到同一个h[k]的子链表上，最后在该链表上查询目标元素。
题目链接模拟散列表 注：保存过题解
代码如下：（附set做法）
### set#include<iostream>
#include<unordered_map>
#include<string>
#include<algorithm>
#include<set>
using namespace std;
int main() {
set<int> s;
int n;
cin>>n;
while(n--) {
char c;
int x;
cin>>c;
if(c=='I') {
cin>>x;
s.insert(x);
} else {
cin>>x;
if(s.find(x)!=s.end()) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}### 哈希函数法#include<cstring>
#include<iostream>
#include<unordered_map>
#include<string>
#include<algorithm>
using namespace std;
const int N =100010;
int h[N],e[N],ne[N],idx; //类似于邻接表，在哈希函数处理后放入对应位置的链表上，最后查询即可
void insert(int x) {
int k=(x%N+N)%N; //确保余数是正数，否则越界，因为x不一定是正数
e[idx]=x;
ne[idx]=h[k]; //若k相同。则会从头部插入k对应的单链表
h[k]=idx++;
}
bool find(int x) {
int k=(x%N+N)%N;
for(int i=h[k]; i!=-1; i=ne[i]) {
if(x==e[i]) return true; //遍历当前k的链表
}
return false;
}
int main() {
int n;
cin>>n;
//单链表指针指向为空时默认为-1；
memset(h,-1,sizeof h);
while(n--) {
char c;
int x;
cin>>c;
if(c=='I') {
cin>>x;
insert(x);
} else {
cin>>x;
if(find(x)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}字符串hash (字符串前缀hash法)
好处：用O(1)的时间复杂度求出任一子字符串的哈希值
对于某些复杂的KMP问题可以用此方法水过去
预处理前缀字符串，假设字符串为p进制的数，求出它的10进制数并对q取模，则可得到所有前缀的哈希值；如h[1]=”A”,h[2]=”AB”;……其中h[0]规定为0,表示前0个字符为空,且存的不是字符串(“A”,”AB”等)，而是p进制的对应哈希值。
一般的：p进制取131 或 13331 时，冲突的概率较低
q一般取2^64 （类型：unsigned long long） (此时就可以省去取模的运算，更快)
结果：将每个前缀字符串映射成一个在[0 , 2^64-1] 范围内的整数
假如有一个字符串 abcdefs;
其中abc的哈希值为 hash(abc), 那么abcd的哈希值就为 hash(abc)*131+4 ; //根据计算10进制过程推出，并且由于mod(q)的原因，不用担心hash值大小
则得出预处理公式：< **hash(i)=hash(i-1)*131+str[i];** > hash[0]=0;
//str存输入的字符串,需要变为对应的序号，如果是全小写字符，则 str[i]-‘a’+1;
纠正：只要str[i]不是0就可以，所以也没必要-‘a’+1，所以就不用担心字符是否为大写小写字母或数字了
求任一子字符串的哈希值 (前提：求出预处理前缀字符串的哈希值)
求[L,R]的哈希值，*h(L–R) = h[R]-h[L-1]131^(R-L+1); 即：在求字符串abcd的子串cd 哈希值的时候，可以用hash(abcd)减去hash(ab)*131^2; 这样就可求出。
而131的次方 提前预处理存入p[N]数组中, p[i] 对应131^i *p[i]=p[i-1]base;
又如：区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，
乘上 P2 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。
例题：[兔子与兔子](138. 兔子与兔子 - AcWing题库) 注意：此题字符串仅有小写字母
#include<iostream>
#include<cstring>
using namespace std;
const int N =1000010,base=131;
typedef unsigned long long ull;
char str[N];
int m;
ull h[N]; //存放前缀字符串的哈希值
ull p[N]; //存放计算10进制时的131次方,可以理解为从个位数往前按位数乘的131次方
ull get(int l,int r){
return h[r]-h[l-1]*p[r-l+1]; //得出l到r区间的hash值
}
int main(){
scanf("%s",str+1);
int n=strlen(str+1); //加头文件string.h
h[0]=0; //初始化0位置
p[0]=1; //初始化个位数*的次方
for(int i=1;i<=n;i++){
h[i]=h[i-1]*base + str[i]-'a'+1;
p[i]=p[i-1]*base;
}
cin>>m;
while(m--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(get(l1,r1)==get(l2,r2)) puts("Yes");
else puts("No");
// printf("%llu\n",get(l,r));
}
// for(int i=1;i<=n;i++){
// printf("%llu\n",h[i]); //测试hash值
// }
return 0;
}注：这种方法可以过全部样例，如果时间有限，用string的substr(pos,n) 可以过一定的样例骗点分，但是还是多用哈希这种方法，还是很容易熟悉的。
substr从第pos个位置，开始拿出n个字符组成的字符串
例题2:[字符串哈希](841. 字符串哈希 - AcWing题库)
该题与上题的不同在于 字符串中不止小写字母，还有大写字母和数字。
但是纠正后，str[i]只要不等于0都可以。所以方法相同。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N =100010,base=131;
typedef unsigned long long ull;
char str[N];
int n,m;
ull h[N];
ull p[N];
ull get(int l,int r){
return h[r]-h[l-1]*p[r-l+1]; //得出l到r区间的hash值
}
int main() {
cin>>n>>m;
scanf("%s",str+1);
h[0]=0;
p[0]=1; //忘记初始化了
for(int i=1;i<=n;i++){
h[i]=h[i-1]*base + str[i];
p[i]=p[i-1]*base;
}
while(m--){
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(get(l1,r1)==get(l2,r2)) puts("Yes");
else puts("No");
// printf("%llu %llu\n",get(l1,r1),get(l2,r2));
}
return 0;
}Trie字典树 (检索)
高效地存储和查找字符串集合的数据结构
存储: 星号为标记一个字符串结束
从根结点开始，只要遇到某个字符不存在就创建该结点
查找：遍历待查找字符串，从根结点开始找对应的下一字符
字符串统计
插入字符串，查找字符串出现的个数
用map做结果：
通过了 18/18个数据 运行时间： 111 ms 运行空间： 480 KB
用Trie字典树高效存储：
通过了 18/18个数据 运行时间： 58 ms 运行空间： 10584 KB
空间换时间 (感觉map能过就不用trie了)
代码如下：
#include<iostream>
#include<string>
using namespace std;
const int N =100010;
int son[N][26]; //假如是son[1][2]=3;说明结点1有一个结点为3的儿子c (从0开始表示a……z); 并且每个结点最多有26个分支
int cnt[N],idx; //cnt记录某个结点作为字符串结尾的次数
char str[N];
void insert(char str[]){
int p=0; //类似指针，指向每一个要插入的子结点的父母
//这里str[i]用了字符串特性：结尾的 '/0'
for(int i=0;str[i];i++){
int u=str[i]-'a'; //将每个字符转化为数字
if(!son[p][u]) son[p][u]=++idx; //如果不存在该字符,新建一个并给孩子编号
p=son[p][u]; //p指针移向当前结点的子结点，进行下一步插入
}
cnt[p]++; //循环结束后，p指向的是字符串str的最后一个结点
}
//查询，返回字符串出现的次数
int query(char str[]){
int p=0;
for(int i=0;str[i];i++){
int u=str[i]-'a';
if(!son[p][u]) return 0; //如果当前结点p不存在相应的孩子，则说明无这个字符串，直接返回
//否则就将结点p指向子孩子对应的结点
p=son[p][u];
}
return cnt[p]; //返回以当前字符为结尾的字符串个数
}
int main(){
int n;
cin>>n;
while(n--){
char c[2];
scanf("%s",c);
if(c[0]=='I'){
scanf("%s",str);
insert(str);
}else {
scanf("%s",str);
printf("%d\n",query(str));
}
}
return 0;
}最大异或对
暴力双层循环过5/9样例
trie树做法：将每个数的二进制数插入字典树，查找时，在每一部选择上尽量选与当前位数不同的路，这样得到的结果是最大的异或数。
points：
1.二进制序列得到10进制数
2.二进制位运算 a>>k&1;
3.选择路径
代码如下：
/*> 时间复杂度分析：用trie树在每一位二进制数中选择与当前目标数不同位的一条路，这样得到每一位尽可能的不同，
最后得到的数就是最大异或数；
这样最多10万个数，每个数最多走31条路(31次)，所以 31*1e5 大概是O(nlogn);
*/
#include<iostream>
#include<string>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N =100010;
const int M =N*31; //每个数的二进制数都有31位，所以要存这么多结点需要开M
//数据范围在2^31之内，则二进制数最多31位,则a二进制数的最左端是第30位
int son[M][2],idx;
void insert(int &a){
int p=0;
for(int i=30;i>=0;i--){
int u=a>>i&1; //取a的二进制数的第30位，注意位数是从右往左0开始计数
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
}
//查询哪一个数与目标数的异或结果最大，返回该数
int query(int a){
int res=0;
int p=0;
for(int i=30;i>=0;i--){
int u = a>>i&1;
//尽量走与当前位不同值的路 !u为非运算，x->0 0->x （x为大于0的数）
//如果相反的路存在，就走这条路,否则就直接走下一条
if(son[p][!u]) {
p=son[p][!u];
res=res*2+!u;
}
else {
p=son[p][u];
res=res*2+u;
}
}
return res;
/*
这里的res=res*2+!u/u的运算，实际上就是2进制转10进制的运算,假如1001要接上下一位数1或0，变成10010或10011，
可以把1001左移一位得到10010,最后在最后一位加上u/!u,而左移一位相当于*2。
这样的操作可以得到对应二进制序列代表的10进制数
*/
}
int main(){
IOS;
int n;
cin>>n;
//不需要实际读入，记录一下res即可 ,当然也可以存数组
int res=0;
for(int i=0;i<n;i++) {
int a;
cin>>a;
insert(a);
int s=query(a);
res=max(res,a^s);
}
cout<<res<<endl;
return 0;
}并查集
主要完成两个操作： 时间复杂度可以接近O(1)
1.合并集合 2.询问两个数是否在同一个集合中
如果需要用到这两个操作可以使用并查集
思路：将每个集合（树）的根结点作为代表结点，并将该集合的每一个结点的父结点存储下来，p[x]存储x的父结点的编号
(1).判断树根：
判断当前结点是否为树根就看当前( p[x]==x )是否成立
(2).求x对应的树根编号，即得到x所在集合的编号
从当前结点，依次往父结点靠拢，并判断是否为根结点
while(p[x]!=x){ x=p[x]; } //最后x就为根结点的编号路径压缩优化 ：由于从x位置遍历到根结点，所以树层数高的时候复杂度较高
在往上遍历时，直到找到根结点，就把所有路经上的结点的父结点变为根结点
核心递归操作 int find(int x){ //返回x的祖宗结点+路径压缩 if(p[x]!=x) p[x]=find(p[x]); return p[x]; //直到某个结点的父结点是根结点后返回，这样就可以将路径 //上所有的结点的父结点变成根结点 }将两棵树中其中一颗的根结点变成另一颗树的孩子，这样就可以查找时有共同的根结点，即在一个集合中。
假设x集合的根结点编号为a，y集合的根结点编号为b 则 p[a]=b; or p[b]=p[a];
y总视频课笔记：参考
合并集合
#include<iostream>
using namespace std;
const int N =100010;
int p[N]; //存放父结点
int n,m;
int find(int x){ //寻找祖宗结点+路径压缩
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
p[i]=i; //初始化每个数独自成集合 ,注意每个数是1--n范围内
}
while(m--){
char op[2];
scanf("%s",op);
int a,b;
scanf("%d%d",&a,&b);
int c=find(a),d=find(b);
if(op[0]=='M'){
if(c!=d) p[c]=d; //如果不在同一个集合，就进行合并，即将一个集合的根结点作为另一个集合的孩子
}else {
if(c==d)
puts("Yes");
else puts("No");
}
}
return 0;
}连通块中点的个数
连通指a可以到b，b可以到a
实际上和集合是差不多的，只要两个数在一个集合了，就一定可以互相到达，因此只需要关注第三个操作，前两个操作都是一样的；
第三个操作：询问连通块中点的数量(集合的元素个数)
定义一个cap[N]数组存储每个集合根结点的元素个数，共有两个部分
1.初始化时每个集合大小都为1，且点独自为一个集合
2.合并集合时，其中一个集合的根结点被当作另一个集合的孩子时，另一个集合的大小要加上这个集合 即 p[find(a)]=find(b); cap[find(b)]+=cap[find(a)];
代码如下：
#include<iostream>
using namespace std;
const int N =100010;
//连通块其实类似于集合，只要在同一个集合，就可以达到连通的效果
//并且本题的前两个操作很类似集合的操作，可模仿
//第三个操作需：合并集合时，维护集合大小
int n,m;
int p[N];
int cap[N]; //记录每个根结点代表的集合中点的个数
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main() {
cin>>n>>m;
for(int i=1;i<=n;i++) {
p[i]=i;
cap[i]=1; //初始化小集合和大小
}
while(m--){
char op[2];
scanf("%s",op);
int a,b,c=0,d=0;
if(op[0]=='C'){
scanf("%d%d",&a,&b);
c=find(a),d=find(b);
if(c==d) continue; //如果两者已经在一个集合里了，就不要再合并了，否则集合大小有问题
cap[d]+=cap[c]; //合并集合时，注意要维护一下新的根结点对应集合的大小
p[c]=d;
}else if(op[1]=='1'){
scanf("%d%d",&a,&b);
c=find(a),d=find(b);
if(c==d) puts("Yes");
else puts("No");
}else if(op[1]=='2'){
scanf("%d",&a);
cout<<cap[find(a)]<<endl;
}
}
return 0;
}食物链
话不多说了，代码含注释
/* 思路：实际上也是集合的合并以及判定，区别在于我们需要判断是否满足与题目要求的三点相符（假话条件）
我们可以在不同维度上(x+n,x+n+n)上额外定义某动物x的捕食域和天敌域
根据条件得到假话个数
*/
#include<iostream>
using namespace std;
const int N =2e5+10; //捕食域，天敌域分别存放在x+n和x+n+n的维度上 ,省去多开数组的麻烦
int p[N];
int n,k;
int ans; //记录假话个数
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
//需反复用到合并集合的操作，定义一个函数 此处定义的是x所在集合接到y所在集合
void merge(int x,int y){
p[find(x)]=find(y);
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=3*n;i++) p[i]=i; //初始化所有域
while(k--){
int d,x,y;
scanf("%d%d%d",&d,&x,&y);
if(x>n||y>n)
ans++;
else if(d==1){ //如果x和y是同类 但是y的捕食域有x，或y的天敌域有x，则是假话
if(find(x)==find(y+n)||find(x)==find(y+n+n))
ans++;
else { //既然是同类，那么他们的捕食和天敌应是一样的
merge(x,y);
merge(x+n,y+n);
merge(x+n+n,y+n+n);
}
}else { //如果x捕食y 但是x和y是同一个动物、同一类动物、x的天敌域中有y、y的捕食域有x 则是假话
if(x==y||find(x)==find(y)||find(y+n)==find(x))
ans++;
else {
merge(x+n,y); //x的捕食域加入y
merge(x,y+n+n); //y的天敌域加入x
merge(x+n+n,y+n); //根据题目说明，y如果是被x吃，那么y就能吃x的天敌，则y的捕食域加入x的天敌
}
}
}
cout<<ans<<endl;
return 0;
}堆排序
与堆有关的STL：STL—heap概述及用法 - Bill_LHR - 博客园 (cnblogs.com)
主要是建立大根堆小根堆
堆是一颗完全二叉树
小根堆的概念：
每个结点小于等于它的左右孩子，则根结点就是最小值
存储方式（与完全二叉树相同）：一维数组
从1开始存，1位置是根结点,x的左孩子下标为2x,右孩子下标为2x+1
主要的两个操作 down(x),up(x); 调整堆为小根堆的操作
down的操作是如果x变大，就要将其向下每一步与最小的孩子交换，最终重新成为小根堆；
up是x变小，将其向上如果小于父结点就进行交换，最终得到新的小根堆
手写堆排序
主要的操作：
STL可支持前三个操作(但后两个可以间接实现)
1.插入一个数
2.求集合中的最小值
3.删除最小值
4.删除任意一个元素
5.修改任意一个元素
插入和删除的时间复杂度与树高度有关，则为logn
1.插入一个数到堆中，并调整为小根堆 插入到末尾后往上移
heap[++size]=x; up(size);2.删除最小值
将最后一个元素heap[size]覆盖根结点heap[1],后size–，再进行down(1);调整即可
heap[1]=heap[size]; size--; down(1);3.删除任意一个元素,删去第k个位置的数
将最后一个元素heap[size]覆盖到第k个元素heap[k]，size–;最后调整第k个位置，
这里可以判断如果数变小了就上移up(k),否则变大了down(k);
//直接上下调整一下更方便 heap[k]=heap[size]; size--; down(k),up(k); //或者判断一下，但是还要存temp： temp=heap[k]; heap[k]=heap[size]; size--; if(temp>heap[k]) up(k); //变小了 else if(temp<heap[k]) down(k);4.修改任意一个元素
heap[k]=x; down(k),up(k);
[堆排序](838. 堆排序 - AcWing题库)
如题。
本题只需要使用到down进行小根堆的生成和建立
代码实现：
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int h[N];
int cap; //size好像有冲突，还是用cap吧 (capcity)
int n,m;
//down，如果当前结点不满足小根堆条件，就和它的最小的孩子进行交换，直到不能交换为止
void down(int u){
int t=u;
//如果它的左孩子存在并且大于左孩子就与左孩子交换
if(u * 2 <= cap && h[t]>h[u*2]) t=u*2;
//如果右孩子结点小于左孩子，就交换根结点与右孩子，否则就与左孩子交换
if(u * 2 + 1 <=cap && h[t]>h[u*2+1]) t=u*2+1;
//如果发生交换了，就下标对应的值交换,并且将这个数继续向下比较，直到不能交换为止
if(t!=u){
swap(h[t],h[u]);
down(t);
}
}
int main(){
cin>>n>>m;
cap=n;
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
for(int i=n/2; i ;i--){ //树的最后一层不需要down，从倒数第二层开始进行每个元素的down即可生成小根堆
down(i);
}
while(m--){
//依次输出堆顶元素即最小值
printf("%d ",h[1]);
//输出后删去
h[1]=h[cap]; cap--; down(1);
}
return 0;
}
