二叉堆

介绍

二叉堆主要支持的操作有：插入一个数 \(O(\log n)\)、查询最小值 \(O(1)\)、删除最小值 \(O(\log n)\)。

二叉堆是一棵完全二叉树，其每个节点都有一个值，且每个节点的值都大于等于/小于等于其父亲的值。每个节点的值都大于等于其父亲值的堆叫做小根堆（即根最小），否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

模板——图论

Floyd 算法，SPFA 算法（慎用），Dijkstra 算法，Tarjan 算法，Prim 算法，Kruskal 算法，欧拉路，Dinic。

模板——杂项

KMP，LCA，SG 函数，二进制相关，数位 DP，费马平方和定理，对抗搜索，神秘康托展开，cout 输出流控制，三分（整数三分，实数三分），upper_bound 相关，树的一些性质，点分治。

模板——数据结构

ST 表，Trie 树，并查集，笛卡尔树，树上启发式合并，Kruskal 重构树，Bitset，线性基，链表。

模板——数学类

快速幂，质数线性筛，质因数分解，欧几里得（gcd），扩展欧几里得（exgcd），求欧拉函数 \(\varphi(x)\)，欧拉定理，扩展欧拉定理，中国剩余定理（CRT），在任意模意义下的逆元，同余最短路，组合数，Lucas 定理，卡特兰数，递推求逆元，拉格朗日插值，康托展开，高斯消元，矩阵快速幂。

• https://codeforces.com/gym/104090/problem/D

找规律 经过手动模拟几轮发现，设钱数总和为 \(s\)，则第一个人分得 \(2s/(n+1)\)，其余人分得 \(s/(n+1)\)。收敛速度很快。

I. Guess Numbers

https://codeforces.com/gym/104828/problem/I

• 求：! x y \(x\) 和 \(y\) 的值。
• 问：? a b 返回 \(\gcd(x+a,y+b)\) 的值。
• 限制询问次数：\(200\)。
• \(0≤x,y<2^{60},0≤a,b<2^{61}\)。

查询排序后的最大公约数

https://leetcode.cn/problems/sorted-gcd-pair-queries/description/

给你一个长度为 \(n(n\le10^5)\) 的整数数组 nums​，值域 \(5·10^4\) 。

两两组合出 \(n^2/2\) 个数对，对每个数对求出 gcd(nums[i], nums[j]) ，并放在一起升序排列成一个数组。

\(q(q\le10^5)\) 个查询，每次询问数组里下标为 \(q_i\) 的数是几。

Problem A

有 \(n\) 个字符串，\(t_1,t_2,…,t_n\)，这些字符串只由字符 s 和 h 组成。 定义这些字符串的连接为 \(t_1,t_2,…,t_n\) 首尾相接。

可以对这 \(n\) 个字符串进行任意次重排，希望重排后字符串的连接之中 sh 子序列出现次数最多，并求出这个最大值。

\(1≤n≤10^5\)，总长度不超过 \(10^5\)。

G. Omg Graph

https://codeforces.com/contest/2117/problem/G

给定无向带权连通图，定义一条路径的花费为：路径经过的边中，边权最大值 + 最小值。求从 \(1\) 到 \(n\) 路径中的最小花费（注意不一定是简单路径）。

\(2≤n≤2⋅10^5,n−1≤m≤\min(2⋅10^5,n(n−1)/2),1≤u,v≤n,1≤w≤10^9\)