1，优先队列

优先队列：就是一个堆，可以维护一个集合的最大值（或者最小值），以在很优秀的时间复杂度（log级别）
内进行查询top(),插入push（），和删除（）pop（）
例题：蓝桥杯官网————一道简单的取模问题

代码：

#include <iostream>
#include<queue>
using namespace std;
using ll = long long;
//正常模拟会超时
//采用优先队列
priority_queue<ll>pq;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        ll x = 0; cin >> x;
        sum += x;
        pq.push(x);
    }
    for (int i = 1; i <= q; i++)
    {
        ll x; cin >> x;
        while (pq.top() >= x)
        {
            ll y = pq.top(); pq.pop();//将顶端元素赋值给y，并出队
            sum += y % x - y;
            pq.push(y % x);//如果队列顶端元素>=x，就进行取模操作，并入队且取和，否则原封不动
        }
        cout << sum << ' ';
    }
    return 0;
}

//////堆的结构
//堆是一种二叉树，其满足：儿子的权值都比自己的权值小（大根堆）或相等或大（小根堆）
// 这个性质不断向上传递直到根，保证根的权值是整棵树中最大的/最小的！
// 手写堆：
// 手写堆需要实现一下几个函数
// 1,pushup()将某个点向上更新，一般是将最后一个点向上更新
// 2,pushdown()将某个点向下更新，一般将根向下更新
// 3，push()插入一个点到堆内
// 4,pop()将根节点删除
// 我们采用数组的方式来存储数据，利用二叉树的性质：2x表示x的儿子编号，2x+1表示x的右儿子编号
// 用sz表示节点数量，a[x]表示节点x的权值
// 代码示例：
/*这段代码实现了一个最大堆（大顶堆）的数据结构，下面详细解释其实现原理和各函数功能：
堆的基本概念
最大堆是一种完全二叉树，每个节点的值都大于或等于其子节点的值。堆通常用数组实现，其中：
数组索引从 1 开始，方便计算父子关系。
节点x的左子节点为x << 1（即2x），右子节点为x << 1 | 1（即2x+1）。左移补0乘以2，右移补符号位除以2！！！
节点x的父节点为x >> 1（即x/2）。*/

以下是对每个函数的详解（以大根堆为例）：

1，pushup

void pushup(int x)//x：节点编号
{
    while (x != 1)//只要不是根节点，就一直跟父节点比较，并更新
    {
        if (a[x] > a[x >> 1])swap(a[x], a[x >> 1]), x >>=1;
        else break;//如果到某个位置停下了就退出
    }
}

功能：将节点x向上调整，维护最大堆性质。
实现逻辑：
从节点x开始，不断与父节点比较。
若当前节点值大于父节点，则交换两者，并继续向上调整（更新x为父节点）。
若当前节点不大于父节点，则停止调整。

2，pushdown

//pushdown要分情况讨论
//例子：
void pushdown(int x)
{
    //如果没有儿子
    if ((x << 1) > sz)return;//在堆的实现中，sz 通常表示 堆的当前大小（即堆中元素的数量），
    //同时也对应数组中最后一个元素的索引。它是一个全局变量或类成员变量，用于跟踪堆的状态。
    //当2x > sz时，意味着左子节点超出了数组的范围，说明节点x没有子节点，此时直接返回
    
    //如果有左儿子但是没有右儿子
    if ((x << 1 | 1) > sz)
    {
        if (a[x << 1] > a[x])
        {
            swap(a[x], a[x << 1]);
            pushdown(x << 1);
        }
    }//若2x + 1 > sz，则表明右子节点不存在，节点x仅有左子节点。因为若x没有左节点则会返回，所以此时
    //x必有左节点
    /*要是左子节点的值比当前节点大，就把它们交换。
交换之后，可能会破坏左子树的最大堆性质，所以要递归调用pushdown函数对左子树进行调整*/
    
    //注：为什么没有“有右儿子但没有左儿子”的情况？
    //因为有右儿子就一定会有做儿子，毕竟2x+1<=sz,2x必定<=sz!!!

    else//左右儿子都有
    {
   /*比较容器最大值，当节点x的值大于或等于左右子节点的值时，说明该节点已经处于正确位置，直接返回。*/
        if (a[x] == max({ a[x] , a[x << 1], a[x << 1 | 1] }))return;
        if (a[x << 1] > a[x << 1 | 1])//为什么要比较左右儿子？
        //当节点 x 有两个子节点时，需要确保它与较大的子节点交换
       /*维持父节点最大：若 x 小于子节点，则必须与较大的子节点交换，才能保证新的父节点值最大。
避免破坏子树结构：若选择较小的子节点交换，可能导致较大的子节点成为新父节点的子节点，从而违反堆性质。*/
        {
            swap(a[x], a[x << 1]);
            pushdown(x << 1);
        }
        else
        {
            swap(a[x], a[x << 1 | 1]);
            pushdown(x << 1 | 1);
        }
    }
}
//举例：假设堆的数组为 [3, 7, 8]（对应二叉树 3(root) -> 7(left), 8(right)），
// 对根节点 x=1（值为 3）调用 pushdown：
//若这里将7和3交换则8还是比7大，不符合规则l，所以要一次性将3和8交换
// 以确保父节点最大！
//

//该函数的时间复杂度是 O (log n)，这里的 n 是堆的大小。

功能：将节点x向下调整，维护最大堆性质。
实现逻辑：
无子节点：直接返回。
只有左子节点：若左子节点大于当前节点，交换并递归调整左子树。
左右子节点都有：
若当前节点已是最大值，无需调整。
否则，选择较大的子节点交换，并递归调整被交换的子树

3，push

void push(int x)
{
    a[++sz] = x;//先将sz加一，再插入新元素（表示第sz+1个元素是x）
    pushup(sz);
}

功能：向堆中插入新元素x。
实现逻辑：
将新元素添加到数组末尾（a[++sz] = x）。
调用pushup(sz)将新元素向上调整到正确位置

3，pop

void pop()
{
    a[1] = a[sz--];//先将sz的元素覆盖第一个元素，再将sz减一（表示元素剩下sz-1个）
    pushdown(1);
}

功能：删除堆顶元素（最大值）。
实现逻辑：
用数组最后一个元素覆盖堆顶元素（a[1] = a[sz--]）。
调用pushdown(1)将新堆顶向下调整到正确位置。

例题：还是上面那道

#include <iostream>
#include<algorithm>
using namespace std;
using ll = long long;
const ll N = 1e5 + 9;
ll a[N * 4];
ll sz = 0;
//采用堆来解题
//题目要求最大堆！
//向上调整

/*堆的作用
动态维护最大值：
堆顶元素始终是当前集合的最大值，使得每次查询时能快速找到需要处理的元素（≥x 的最大值）。
取模操作后，新元素可能不再是最大值，堆会自动调整，确保下次堆顶仍是最大值。
高效调整：
每次插入和删除操作的时间复杂度为 O (log n)，适合处理大规模数据。
通过堆的自动调整，避免了暴力扫描整个数组，显著优化了时间复杂度。*/
void pushup(int x)
{
    while (x != 1)
    {
        if (a[x >> 1] < a[x])
        {
            swap(a[x >> 1], a[x]);
            x >>= 1;
        }
        else break;
    }
}
//向下调整
void pushdown(int x)
{
    //如果没有儿子
    if ((x << 1) > sz)return;//记得内部加括号！！！否则会混淆，导致答案出错！！！
    //如果有左孩子，没有右孩子
    if ((x << 1 | 1) > sz)
    {
        if (a[x << 1] > a[x])
        {
            swap(a[x << 1], a[x]);
            pushdown(x << 1);//切忌写成a[x<<1],后面也是如此！
        }
    }
    else//左右两个孩子都有
    {
        if (a[x] == max({ a[x],a[x << 1],a[x << 1 | 1] }))return;
        //比较左右儿子
        if (a[x << 1] > a[x << 1 | 1])
        {
            swap(a[x << 1], a[x]);
            pushdown(x << 1);
        }
        else
        {
            swap(a[x << 1 | 1], a[x]);
            pushdown(x << 1 | 1);
        }
    }
}
void push(int x)
{
    a[++sz] = x;
    //pushup(x);push是对编号进行操作，不是x权值
    pushup(sz);
}
void pop()
{
    //a[sz--]=a[1];
    a[1] = a[sz--];//一定要弄清是谁赋值给谁！！！
    pushdown(1);//删去之后还要重新向下调整！！！
}

ll top()
{
    return a[1];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        ll x = 0; cin >> x;
        sum += x;
        push(x);
    }
    for (int i = 1; i <= q; i++)
    { 
        ll x; cin >> x;
        while (top() >= x)
        {
            ll y = top();
            pop();
            sum += y % x - y;
            push(y % x);//如果队列顶端元素>=x，就进行取模操作，并入栈且取和，否则原封不动
        }
        cout << sum << ' ';
    }
    return 0;
}

ok了！制作不易，希望大家关注+点赞+收藏！！！