并查集是一种数据结构，可以比较方便的处理集合的合并、查询、添加，比如查询一个元素属于哪个集合、两个元素是否再一个集合中，合并两个不同的集合
堆是一种特殊的数据结构，通常可以看作一棵树的数组对象，堆总是一个完全二叉树，
堆有大根堆和小根堆，大根堆是每个节点都小于他的父节点，小根堆是每个节点都大于他的父节点

合并集合

一共有 nn 个数，编号是 1∼n1∼n，最开始每个数各自在一个集合中。

现在要进行 mm 个操作，操作共有两种：

1. M a b，将编号为 aa 和 bb 的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
2. Q a b，询问编号为 aa 和 bb 的两个数是否在同一个集合中；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

1≤n,m≤10⁵

输入样例：

4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

Yes
No
Yes

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int ne[N];

int find(int a){
    if(a!=ne[a])ne[a]=find(ne[a]);//找祖节点的时候使用递归的方法顺便更新各个节点的祖节点，最后返回祖节点
    return ne[a];
}

void mm(int a,int b){
    ne[find(a)]=find(b);
}

void qq(int a,int b){
    if(find(a)==find(b)){
        cout<<"Yes\n";
        return;
    }
    cout<<"No\n";
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)ne[i]=i;
    while(m--){
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='M'){
            mm(a,b);
        }else if(c=='Q'){
            qq(a,b);
        }
    }
    return 0;
}

连通块中点的数量

给定一个包含 nn 个点（编号为 1∼n1∼n）的无向图，初始时图中没有边。

现在要进行 mm 个操作，操作共有三种：

1. C a b，在点 aa 和点 bb 之间连一条边，aa 和 bb 可能相等；
2. Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，aa 和 bb 可能相等；
3. Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 nn 和 mm。

接下来 mm 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果 aa 和 bb 在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点 aa 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤10⁵

输入样例：

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

Yes
2
3

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int ne[N],con[N];

int find(int a){
    if(a!=ne[a]){
        ne[a]=find(ne[a]);
    }
    return ne[a];
}
void q1(int a,int b){
    if(find(a)==find(b))cout<<"Yes\n";
    else cout<<"No\n";
}
void q2(int a){
    cout<<con[find(a)]<<endl;
}
void cc(int a,int b){
    int x = find(a);
    int y = find(b);
    if(x!=y){//要注意a,b可能已经在相同的集合中，避免多加所以要判断一下
        ne[find(a)]=find(b);
        con[y]+=con[x];
    }
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        ne[i]=i;
        con[i]=1;
    }
    while(m--){
        string s;
        int a,b;
        cin>>s;
        if(s=="C"){
            cin>>a>>b;
            cc(a,b);
        }else if(s=="Q1"){
            cin>>a>>b;
            q1(a,b);
        }else{
            cin>>a;
            q2(a);
        }
    }
    return 0;
}

食物链

动物王国中有三类动物 A,B,CA,B,C，这三类动物的食物链构成了有趣的环形。

AA 吃 BB，BB 吃 CC，CC 吃 AA。

现有 NN 个动物，以 1∼N1∼N 编号。

每个动物都是 A,B,CA,B,C 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 NN 个动物所构成的食物链关系进行描述：

第一种说法是 1 X Y，表示 XX 和 YY 是同类。

第二种说法是 2 X Y，表示 XX 吃 YY。

此人对 NN 个动物，用上述两种说法，一句接一句地说出 KK 句话，这 KK 句话有的是真的，有的是假的。

当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

1. 当前的话与前面的某些真的话冲突，就是假话；
2. 当前的话中 XX 或 YY 比 NN 大，就是假话；
3. 当前的话表示 XX 吃 XX，就是假话。

你的任务是根据给定的 NN 和 KK 句话，输出假话的总数。

输入格式

第一行是两个整数 NN 和 KK，以一个空格分隔。

以下 KK 行每行是三个正整数 D，X，YD，X，Y，两数之间用一个空格隔开，其中 DD 表示说法的种类。

若 D=1D=1，则表示 XX 和 YY 是同类。

若 D=2D=2，则表示 XX 吃 YY。

输出格式

只有一个整数，表示假话的数目。

数据范围

1≤N≤500001≤N≤50000,
0≤K≤100000

输入样例：

100 7
1 101 1 
2 1 2
2 2 3 
2 3 3 
1 1 3 
2 3 1 
1 5 5

输出样例：

3

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int d[N],p[N];

int find(int x){
    if(x!=p[x]){
        int t=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=t;
    }
    return p[x];
}
int main(){
    int n,k,res=0;
    cin>>n>>k;
    for(int i=1;i<=n;i++)p[i]=i;
    while(k--){
        int a,x,y;
        cin>>a>>x>>y;
        if(x>n||y>n){
            res++;
        }else{
            if(a==1){
                int px=find(x),py=find(y);
                if(px==py&&(d[x]-d[y])%3)res++;
            else{
                if(px!=py){
                    p[px]=py;
                    d[px]=d[y]-d[x];
                }
            }
            }else{
                int px=find(x),py=find(y);
                if(px==py&&(d[x]-d[y]-1)%3)res++;
                else{
                    if(px!=py){
                        p[px]=py;
                        d[px]=d[y]+1-d[x];
                    }
                }
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

堆排序

输入一个长度为 nn 的整数数列，从小到大输出前 mm 小的数。

输入格式

第一行包含整数 nn 和 mm。

第二行包含 nn 个整数，表示整数数列。

输出格式

共一行，包含 mm 个整数，表示整数数列中前 mm 小的数。

数据范围

1≤m≤n≤10⁵1≤m≤n≤10⁵，
1≤数列中元素≤10⁹

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

//好理解但超时
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],n,m,ans;
void ss(int x){//以下标为x的节点为根节点开始构造大根堆
    int zz=2*x+1,yy=2*x+2;//算出根节点x的左右孩子的下标
    /*判断孩子的下标是否在数组内如果孩子的值大于根节点的值就交换，然后递归构造以孩子为根节点的大根堆*/
    if(zz<ans&&a[zz]>a[x]){
        swap(a[x],a[zz]);
        ss(zz);
    }
    if(yy<ans&&a[yy]>a[x]){
        swap(a[x],a[yy]);
        ss(yy);
    }
}

int main(){
    cin>>n>>m;
    ans=n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        for(int j=n-1-i;j>0;j--){
            if(j%2){
                ss((j-1)/2);
            }else{
                ss((j-2)/2);
            }
        }
        swap(a[0],a[--ans]);
    }
    for(int i=0;i<m;i++)cout<<a[i]<<" ";
    return 0;
}
//进行初步优化用b数组记录处理过的根节点，后面再次遇到这个节点时跳过，但是也超时
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],n,m,ans,b[N];
void ss(int x){
    int zz=2*x+1,yy=2*x+2;
    if(zz<ans&&a[zz]>a[x]){
        swap(a[x],a[zz]);
        ss(zz);
    }
    if(yy<ans&&a[yy]>a[x]){
        swap(a[x],a[yy]);
        ss(yy);
    }
}

int main(){
    cin>>n>>m;
    ans=n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        memset(b,0,sizeof(b));
        for(int j=n-1-i;j>0;j--){
            if(j%2&&b[(j-1)/2]==0){
                ss((j-1)/2);
                b[(j-1)/2]=1;
            }else if(b[(j-2)/2]==0){
                ss((j-2)/2);
                b[(j-2)/2]=1;
            }
        }
        swap(a[0],a[--ans]);
    }
    for(int i=0;i<m;i++)cout<<a[i]<<" ";
    return 0;
}
/*ac代码，这是用大根堆处理的，用小根堆处理就是先处理一遍，然后直接输出堆顶
再将堆顶与当前数组的最后一个元素互换然后对堆顶进行构造小根堆，循环处理*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],n,m,ans,b[N];
void ss(int x){
    int zz=2*x+1,yy=2*x+2;
    int t=x;
    if(zz<ans&&a[zz]>a[t])t=zz;
    if(yy<ans&&a[yy]>a[t])t=yy;
    if(x!=t){
        swap(a[x],a[t]);
        ss(t);
    }
}

int main(){
    cin>>n>>m;
    ans=n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int j=ans-1;j>0;j--){
        if(j%2&&b[(j-1)/2]==0){
            ss((j-1)/2);
            b[(j-1)/2]=1;
        }else if(b[(j-2)/2]==0){
            ss((j-2)/2);
            b[(j-2)/2]=1;
        }
    }
    while(ans){
        swap(a[0],a[--ans]);
        ss(0);
    }
    for(int i=0;i<m;i++)cout<<a[i]<<" ";
    return 0;
}

大佬题解–>AcWing 838. 堆排序–海绵宝宝来喽 – AcWing

模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：

1. I x，插入一个数 xx；
2. PM，输出当前集合中的最小值；
3. DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
4. D k，删除第 kk 个插入的数；
5. C k x，修改第 kk 个插入的数，将其变为 xx；

现在要进行 NN 次操作，对于所有第 22 个操作，输出当前集合的最小值。

输入格式

第一行包含整数 NN。

接下来 NN 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。

输出格式

对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。

每个结果占一行。

数据范围

1≤N≤10⁵1≤N≤10⁵
−10⁹≤x≤10⁹−10⁹≤x≤10⁹
数据保证合法。

输入样例：

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例：

-10
6

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
//a数组存堆的值，ph数组存第k个插入的数的下标k就是下标，hp数组存相应下标对应的值是第几个插入的数
//ans记录当年数组的边界，si记录当前第几个数
int a[N],ph[N],hp[N],ans,si;

void heap_swap(int x,int y){//定义新的排序，同时维护ph和hp数组
    swap(ph[hp[x]],ph[hp[y]]);
    swap(hp[x],hp[y]);
    swap(a[x],a[y]);
}

void down(int x){
    int zz=x*2+1,yy=x*2+2,t=x;
    if(zz<ans&&a[zz]<a[t])t=zz;
    if(yy<ans&&a[yy]<a[t])t=yy;
    if(x!=t){
        heap_swap(x,t);
        down(t);
    }
}

void up(int x){
    a[ans++]=x;
    ph[++si]=ans-1;
    hp[ans-1]=si;
    for(int i=ans-1;i>0;i--){
        if(i%2)down((i-1)/2);
        else down((i-2)/2);
    }
}
int main(){
    int n;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        if(s=="I"){
            int x;
            cin>>x;
            up(x);
        }else if(s=="PM"){
            cout<<a[0]<<endl;
        }else if(s=="DM"){
            heap_swap(0,ans-1);
            ans--;
            for(int i=ans-1;i>0;i--){
                if(i%2)down((i-1)/2);
                else down((i-2)/2);
            }
        }else if(s=="D"){
            int k;
            cin>>k;
            int t=ph[k];
            heap_swap(ph[k],ans-1);
            ans--;
            for(int i=ans-1;i>0;i--){
                if(i%2)down((i-1)/2);
                else down((i-2)/2);
            }
        }else if(s=="C"){
            int k,x;
            cin>>k>>x;
            a[ph[k]]=x;
            for(int i=ans-1;i>0;i--){
                if(i%2)down((i-1)/2);
                else down((i-2)/2);
            }
        }
    }
    return 0;
}

ph数组的下标代表第几个插入，值代表第k个插入的数的下标，ph数组的下标代表对应堆中值的下标，值代表第k个插入
ph [ idx ] = ans 第 idx 个插入的值的下标为 ans
hp [ ans ] = idx 下标为 ans 的值是第 idx 个插入的
a [ ans ] = ??? 下标为 ans 的值为 ？？？