C 对顶堆模板题 动态输出中位数
对顶堆结构高效实现动态计算中位数，用两个堆分别维护序列的两半部分，实时保持平衡并计算中位数
实现代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
//小根堆存大元素，堆顶为这部分的最小值
priority_queue<int,vector<int>,greater<int>> min_heap;
//大根堆存小元素，堆顶为这部分的最大值
priority_queue<int> max_heap;
for(int i = 1,ai;i <= n;i ++){
cin >> ai;
if(max_heap.empty() || ai <= max_heap.top()) max_heap.push(ai);//// 小于等于大根堆顶 → 属于较小一半
else min_heap.push(ai);// // 大于大根堆顶 → 属于较大一半
//// 大根堆元素过多，移一个最大值到小根堆
if(max_heap.size()>min_heap.size() + 1){
min_heap.push(max_heap.top());
max_heap.pop();
}
//// 小根堆元素过多，移一个最小值到大根堆
else if(min_heap.size() > max_heap.size()){
max_heap.push(min_heap.top());
min_heap.pop();
}
if(i & 1) cout << max_heap.top() << " ";//奇数个元素，大根堆顶是中位数
else cout << (max_heap.top()+min_heap.top())/2 << " ";//偶数个元素，两堆顶下取整平均值
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
纯享版：
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n;
cin >> n;
priority_queue<int> l;
priority_queue<int,vector<int>,greater<int>> r;
for(int i = 1,ai;i <= n;i ++){
cin >> ai;
if(l.empty() || ai<= l.top()) l.push(ai);
else r.push(ai);
if(l.size() > r.size()+1){
r.push(l.top());
l.pop();
}else if(r.size() > l.size()){
l.push(r.top());
r.pop();
}
if(i&1) cout << l.top() << " ";
else cout << (l.top()+r.top())/2 << " ";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
思考：
两种 push 操作（插入元素和平衡堆时）均依赖堆的自动调整特性：插入时按元素大小分入左右堆，堆会自动维护顶为最值；平衡时移动堆顶元素，新堆也会自动调整维持特性，无需手动排序，既保证元素划分正确，又能通过平衡维持中位数位置
H 斐波那契 矩阵加速幂 O(log n)
将斐波那契数列的递推关系转化为矩阵运算，再用快速幂加速矩阵高次幂的计算，从而在 O(logn) 时间内解决大 n 的求和问题
一些推导过程：
代码实现：
#include <iostream>
using namespace std;
#define int long long
const int mod = 998244353;
struct Matrix {
int a, b, c, d;
};
Matrix multiply(const Matrix& m1, const Matrix& m2) {
Matrix res;
res.a = (m1.a * m2.a % mod + m1.b * m2.c % mod) % mod;
res.b = (m1.a * m2.b % mod + m1.b * m2.d % mod) % mod;
res.c = (m1.c * m2.a % mod + m1.d * m2.c % mod) % mod;
res.d = (m1.c * m2.b % mod + m1.d * m2.d % mod) % mod;
return res;
}
//eg.M^5:pow_mat(M,5)
Matrix pow_mat(Matrix base, int exp) {
// 1. 初始化结果为「单位矩阵」
Matrix res = {1, 0, 0, 1};//E 1
// 2. 循环处理指数的每一位二进制
while (exp) {// 当指数还没处理完时
// 3. 判断当前二进制位是否为1
if (exp & 1) {
res = multiply(res, base);//把当前base乘入结果
}
// 4. 底数矩阵自乘（翻倍）
base = multiply(base, base);//base变为原来的平方（如M→M²→M⁴→...）
// 5. 指数右移一位（处理下一个二进制位）
exp >>= 1;
}
return res;
}
signed main() {
int n;
cin >> n;
if (n == 0) {
cout << 0 << endl;
return 0;
}
int e = n + 1;//e为所需幂次
Matrix M = {1, 1, 1, 0};//斐波那契转移矩阵
Matrix Mexp = pow_mat(M, e);//矩阵快速幂
//提取 M^(n+1) 矩阵的第一行第一列元素（a），即f(n+2)
int fib = Mexp.a;
//F(n) = f(n+2) - 1;
int ans = (fib - 1 + mod) % mod;
cout << ans << endl;
return 0;
}
矩阵加速幂适用场景：
1.转移矩阵的定制：
根据递推关系设计矩阵（如斐波那契用 [[1,1],[1,0]]，3 阶递推用 3x3 矩阵），矩阵元素直接对应递推系数
2.适用场景：
所有线性递推问题（k 阶递推、带系数递推等），只需调整转移矩阵的维度和元素，即可复用快速幂框架
I 复习两个定理所需的最短时间
树的前缀和与二进制 Lifting 求 LCA
快速找到a和b的最近公共祖先（LCA），是两条祖先链的最深交点，其路径和就是需要减去的重复部分
思路：
1.dfs进行初始化，比如这题的深度，父子节点关系的存储，以及前缀和时间
2.dfs中使用Lifting优化（i++）再去递归dfs子节点
3.lca中再次利用了Lifting（提升操作）（i--），然后分情况，首先先指定a为更深的，然后进行第一步提升a操作，如果b是a的祖先，那么a提升至b位置为止，且此时lca返回节点a即b；如果a和b不存在谁是谁的祖先关系，那么继续第一步提升a操作使a、b现在同一深度，再去（i--）找到某个2的i次方使祖先不同（公共祖先的子节点），返回f[a][0],f[b][0]均可，最后输出dfs中预先处理过的sum表达答案
代码实现：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+10;
int n;
int a[N];
vector<int>tree[N];
int dep[N];
int sum[N];//根至当前节点路径时间和
int f[N][20];//二进制Lifting表：f[u][i]表示u的2^i级祖先
//dfs遍历+预处理，初始化深度、前缀和、祖先表
void dfs(int son, int fa)
{
dep[son] = dep[fa] + 1;
f[son][0] = fa;
sum[son] = a[son] + sum[fa];
//Lifting优化
for (int i = 1; i <= 19; i++)
//走2^i步，即走2^(i-1)步再走2^(i-1)步
f[son][i] = f[f[son][i - 1]][i - 1];
//递归处理子节点
for (int i = 0; i < tree[son].size(); i++)
{
int t = tree[son][i];
if (t != fa)dfs(t, son);//跳过父节点避免循环
}
}
int lca(int a, int b)
{
if (dep[a] < dep[b])swap(a, b);//使a为更深的节点
for (int i = 19; i >= 0; i--)
{
if (dep[f[a][i]] >= dep[b]) a = f[a][i];//快速将a抬升至与b同深度
if (a == b)return a;//情况 1：b为a祖先
//情况2：有共同祖先但互不为祖先
for (int i = 19; i >= 0; i--)
if (f[a][i] != f[b][i])//公共祖先的子节点
{
a = f[a][i];
b = f[b][i];
}
return f[a][0];//equals to f[b][0]
}
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
tree[u].push_back(v);
}
dfs(1, 0);
int q;
cin >> q;
while (q--)
{
int k;
cin >> k;
int a, b;
cin >> a >> b;
cout << sum[a] + sum[b] - sum[lca(a,b)] << endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
京公网安备 11010502036488号